Traveling Salesman Round Trip

You are given n waypoints and m bidirectional roads connecting them. Each road connects two distinct waypoints with a given positive distance. Starting from waypoint 1, your task is to compute the minimum total distance needed to visit every waypoint exactly once and return to the starting point.

If there is no valid route that visits every waypoint and returns to the start, output inf.

The problem can be formulated as finding a minimal Hamiltonian cycle. In mathematical terms, if we denote the set of waypoints by \(\{1, 2, \dots, n\}\) and the distance between waypoints \(i\) and \(j\) by \(d_{ij}\), you are to compute the minimum cost among all cycles of the form:

[ 1 \to \pi(2) \to \pi(3) \to \dots \to \pi(n) \to 1 ]

where \(\pi\) is a permutation of \(\{2, 3, \dots, n\}\).

inputFormat

The first line contains two integers n and m (\(2 \le n \le 10\) and \(1 \le m \le \frac{n(n-1)}{2}\)) representing the number of waypoints and the number of roads respectively.

The next m lines each contain three integers u, v, and d (\(1 \le u, v \le n, u \ne v, 1 \le d \le 10^5\)) indicating there is a road between waypoints u and v with distance d.

It is guaranteed that there is at most one road between any pair of waypoints.

outputFormat

Output a single line containing the minimum total distance of the round trip if such a route exists. Otherwise, output inf (without quotes) if it is impossible to visit every city and return to the start.

## sample

4 6
1 2 10
1 3 15
1 4 20
2 3 35
2 4 25
3 4 30

80