Sightseeing Route

There is a travel agency in Adelton town on Zanzibar island. In addition to many attractions, it offers a sightseeing tour of the town. In order to maximize profit, the agency decided to find the shortest route which starts and ends at the same crossing point while visiting at least 3 distinct crossing points.

In the town there are \(N\) crossing points numbered from 1 to \(N\) and \(M\) two-way roads. Multiple roads may exist between a pair of crossing points, but no road connects a crossing point to itself.

A sightseeing route is given by a sequence of road numbers \(y_1, y_2, \ldots, y_k\) (with \(k > 2\)). For \(1 \le i \le k-1\), the road \(y_i\) connects crossing points \(x_i\) and \(x_{i+1}\), and the road \(y_k\) connects \(x_k\) and \(x_1\). All the crossing points \(x_1, x_2, \ldots, x_k\) must be distinct. The total length of the route is defined as \[ L(y_1)+ L(y_2)+ \cdots + L(y_k), \] where \(L(y_i)\) is the length of road \(y_i\) for \(1 \le i \le k\). Your task is to determine the minimum length of such a sightseeing route. If no valid route exists, output -1.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of crossing points and two-way roads respectively.

Each of the following \(M\) lines contains three integers \(u\), \(v\) and \(w\) indicating that there is a road between crossing points \(u\) and \(v\) with length \(w\). Note that \(1 \le u,v \le N\) and \(u \neq v\). Multiple roads may exist between the same two crossing points.

outputFormat

If a valid sightseeing route exists, print a single integer representing the minimum total length of the route. Otherwise, print -1.

sample

3 3
1 2 1
2 3 1
3 1 1

3