Minimum Delivery Route Length

You are given a delivery network consisting of N intersections and M bidirectional roads. Each road is described by three integers u, v, and w indicating there is a road between intersections u and v with length w.

A delivery truck must start from an intersection, visit every intersection exactly once, and return to the starting point without reusing any road more than once. In other words, the truck must complete a Hamiltonian cycle using only the given roads. Your task is to calculate the minimum total length of such a route. If no such tour exists, output -1.

Note: The truck is allowed to pick any intersection as the starting point. The road network is not necessarily complete, so some pairs might not be directly connected.

The mathematical formulation (if we number intersections from 1 to N) is to find the minimum cost cycle \(C\) among all permutations \(\pi\) of \(\{1,2,...,N\}\) such that:

\[ c(\pi) = w(\pi(N),\pi(1)) + \sum_{i=1}^{N-1} w(\pi(i),\pi(i+1)) \]

If for some consecutive intersections, the road does not exist (i.e. the cost is \(\infty\)), that permutation is not valid.

inputFormat

The first line contains two integers N and M, representing the number of intersections and roads respectively.

This is followed by M lines, each containing three integers u, v, and w indicating that there is a bidirectional road between intersections u and v with length w.

outputFormat

Output a single integer representing the minimum delivery route length. If no valid tour exists, output -1.

## sample

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

80