问题 K: Cactus Circuit

An undirected connected graph is called a cactus, if and only if each edge of it belongs to at most one simple cycle. A simple cycle is a cycle that has no repeated vertices. Note that there is no self loop in the graph, but there may be duplicate edges connect same nodes. There is an old circuit network contains n nodes and m undirected edges, and the network is guaranteed to be a cactus. Each edge (ui , vi) has a durability di , represents the length of time it can transport electricity. Now your job is to choose an activation time si (si ≥ 0) for each edge (ui , vi), then this edge will only transport electricity in the time interval [si , si + di ] . However, this fragile network cannot be disconnected from any node. Firstly, you must ensure that, the edges that can transport electricity at time 0 have connected all the nodes together. After that, once two nodes cannot be connected at a certain moment, the entire power network will immediately collapse. The question now is, how long can you keep this network running? Formally, if your answer is A , then you should have a way to set all si satisfies that, for every real number t ∈ [0, A], all the n nodes are connected by the edges that can transport electricity at time t .

The first line of the input contains an integer T (1 ≤ T ≤ 5), indicating the number of the test cases. For each test case: The first line contains two integers n, m (1 ≤ n ≤ 105 , 1 ≤ m ≤ 2 × 105 ), indicating the number of the nodes and the edges in the circuit network. Then the following m lines, each line contains three integers ui , vi , di (1 ≤ ui , vi ≤ n, ui 6= vi , 1 ≤ di ≤ 109 ) , indicating an edge in the given graph. It’s guaranteed that the graph is a cactus.

For each test case: print one line contains a single integer, indicating the maximum length of time that you can keep this network running.

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

2
5

For the first sample, you can set s1 = s3 = 0, s2 = 1 so all the nodes are connected by edge 1 and edge 3 in time interval [0, 1] , and by edge 2 and edge 3 in time interval [1, 2] .