Cactus Circuit

Problem Description

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 $(u_i,v_i)$ has a durability $d_i$ , represents the length of time it can transport electricity. Now your job is to choose an activation time $s_i\ (s_i\ge 0)$ for each edge $(u_i,v_i)$, then this edge will only transport electricity in the time interval $[s_i,s_i+d_i]$ . 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 $s_i$ satisfies that, for every real number $t\in[0,A]$, all the $n$ nodes are connected by the edges that can transport electricity at time $t$ .

Input

The first line of the input contains an integer $T\ (1\le T\le 5)$, indicating the number of the test cases. For each test case: The first line contains two integers $n,m\ (1\le n\le 10^5, 1\le m\le 2\times 10^5)$, indicating the number of the nodes and the edges in the circuit network. Then the following $m$ lines, each line contains three integers $u_i,v_i,d_i\ (1\le u_i,v_i\le n, u_i\not =v_i, 1\le d_i\le 10^9)$ , indicating an edge in the given graph. It's guaranteed that the graph is a cactus.

Output

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

Sample Input

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

Sample Output

2
5

Hint

For the first sample, you can set $s_1=s_3=0,s_2=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]$ .

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）