Shortest Cycle in a Graph

You are given an undirected graph representing a network of cities connected by bidirectional roads. Each road connects two cities with a given length. A cycle is defined as a path which starts and ends at the same city and contains at least one road. Note that a road which connects a city to itself (a self‐loop) is considered a cycle with the weight of that road.

Your task is to compute the length of the shortest cycle in the graph. If no cycle exists, output -1.

The length of a cycle formed by removing an edge \( (u, v, w) \) and finding a shortest path from \( u \) to \( v \) is given by:

[ \text{cycle_length} = d(u,v) + w ]

where \( d(u,v) \) is the shortest distance between \( u \) and \( v \) after the edge is temporarily removed from the graph. Perform this process for each edge (including self-loops) to determine the overall shortest cycle.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1 M1
u1 v1 w1
...
uM1 vM1 wM1
N2 M2
... 

Here, T is the number of test cases. For each test case, the first line contains two integers: N (the number of cities) and M (the number of roads). The following M lines each contain three integers u, v, w, representing a road connecting city u and city v with length w.

outputFormat

For each test case, output a single line to standard output (stdout) containing the length of the shortest cycle. If no cycle exists, output -1.

## sample

2
4 4
1 2 2
2 3 3
3 4 4
4 1 5
3 2
1 2 6
2 3 7

14
-1

</p>