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.
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] .