Cheapest cycle P18546

You are given an undirected graph with positive costs at the edges. Please compute the cheapest cycle of the graph.

Input

Input consists of several cases, each with the number of vertices n, followed by the number of edges m, followed by m triples x y c to indicate an edge connecting x and y with cost c, where x ≠ y and 1 ≤ c ≤ 10⁶. Vertices are numbered starting from 0. For every pair of vertices, there is at most one edge connecting them. Assume 3 ≤ n ≤ 1000 and n ≤ m ≤ 5n.

Output

For every case, print the cost of the cheapest cycle of the graph.