D. Connecting Villages
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a region with $$$n$$$ villages, after a heavy snowfall, all $$$m$$$ roads have been blocked. Each of these roads connects two villages, and it will take $$$h_i$$$ hours to reopen the $$$i$$$-th road. These times are independent of each other; work is done on all roads simultaneously.

What is the minimum number of hours that must pass for the villages to be connected? That is, for any pair of villages, there exists a route between the two villages that passes through one or more roads that have already been opened.

It is guaranteed that, after enough hours for all roads to be usable, there is a route between every pair of villages.

Input

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

For each case, there is a line with two integers $$$n$$$ and $$$m$$$, the number of villages and the number of roads. This is followed by $$$m$$$ lines, each with three integers $$$u, v, h_i$$$, representing that there is a road between the $$$u$$$-th village and the $$$v$$$-th village that will take $$$h_i$$$ hours to open. The roads are bidirectional.

Output

For each case, print on a line the number of hours that must pass for the villages to be connected.

Scoring

$$$1 \leq T \leq 100$$$

$$$2 \leq n \leq 10^5$$$

$$$1 \leq m \leq 5 \cdot 10^5$$$

$$$1 \leq h_i \leq 10^6$$$

$$$0 \leq u, v \leq n-1$$$

The sum of $$$n+m$$$ for all cases is at most $$$10^6$$$.

It is guaranteed that if all roads can be used, there is a route between every pair of villages.

52 points: $$$n, m, h_i \leq 1000$$$, the sum of $$$n+m$$$ for all cases is at most $$$10^4$$$.

17 points: $$$m = n-1$$$.

31 points: No additional constraints.

Example
Input
2
3 3
0 1 10
0 2 20
1 2 30
4 3
0 1 10
0 2 20
0 3 30
Output
20
30