K. Keeping Cactus Alive
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An undirected connected graph is called a cactus if and only if each of its edges belongs to at most one simple cycle$$$^{\dagger}$$$. Note that the cactus graph contains no self-loops, but may have multiple edges connecting the same pair of nodes.

There is an aging circuit network with $$$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$$$, representing the length of time during which it can transport electricity.

Your task is to choose an activation time $$$s_i ,(s_i \ge 0)$$$ for each edge $$$(u_i, v_i)$$$. Once activated, the edge can transport electricity only in the time interval $$$[s_i, s_i + d_i]$$$.

However, this fragile network must remain connected at all times. First, the edges that can transport electricity at time $$$0$$$ must connect all $$$n$$$ nodes. After that, if at any moment the network becomes disconnected, the entire power system immediately collapses.

The question is: how long can you keep the network running?

Formally, if your answer is $$$A$$$, then there must exist a choice of activation times $$$\{s_i\}$$$ such that for every real number $$$t \in [0, A]$$$, all $$$n$$$ nodes are connected by the edges that can transport electricity at time $$$t$$$.

$$$\dagger :$$$ In this problem, a simple cycle is a pair of a sequence of vertices $$$(v_0, \ldots, v_{L-1})$$$ and a sequence of edges $$$(e_0, \ldots, e_{L-1})$$$ satisfying the following conditions.

  • $$$L\geq 1$$$
  • $$$i\neq j \implies v_i\neq v_j, e_i\neq e_j$$$
  • For $$$0\leq i \lt L- 1$$$, the edge $$$e_i$$$ connects $$$v_i$$$ and $$$v_{i+1}$$$
  • The edge $$$e_{L-1}$$$ connects $$$v_{L-1}$$$ and $$$v_{0}$$$
Input

The first line of the input contains an integer $$$T$$$, indicating the number of the test cases.

For each test case:

The first line contains two integers $$$n,m\ (2\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.

It is guaranteed that for all test cases, $$$\sum n\le 5\times 10^5,\sum m\le 10^6$$$.

Output

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

Example
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
Output
2
5
Note

For the first example, you can set $$$s_1=s_3=0,s_2=1$$$ so all the nodes are connected by edge $$$1$$$ and edge $$$3$$$ in the time interval $$$[0,1]$$$ , and by edge $$$2$$$ and edge $$$3$$$ in the time interval $$$[1,2]$$$ .