Minimum Maximum Travel Time

You are given a road network of intersections connected by roads with various travel times. Your task is to rearrange the roads such that the maximum travel time between any two intersections, when using the optimal subset of the roads (i.e. the Minimum Spanning Tree), is minimized.

This problem can be solved using Kruskal's algorithm with Union-Find data structure. Given the number of intersections n and a list of roads (edges) connecting them along with a travel time for each road, find the edge with the maximum weight in the Minimum Spanning Tree (MST). The answer for each test case is this maximum edge weight, because in the MST you want to minimize the worst-case travel time.

The MST is obtained by choosing n - 1 edges that connect all intersections with minimal total travel time, and the result is the highest weight among these selected edges.

The input will consist of multiple test cases. For each test case you are given the number of intersections and the number of roads, followed by the road information. Output one result per test case on a new line.

inputFormat

The input is provided via standard input (stdin) and has the following format:

T
n1 m1
u1 v1 w1
u2 v2 w2
... (m1 lines)
n2 m2
... (m2 lines)
... (T test cases)

</p>

Where:

• T is the number of test cases.
• For each test case:
• n is the number of intersections (vertices).
• m is the number of roads (edges).
• Each of the next m lines contains three integers u, v, and w indicating a road between intersections u and v with travel time w.

outputFormat

For each test case, output a single integer representing the maximum travel time (the largest edge weight in the Minimum Spanning Tree) on a new line.

The output should be written to standard output (stdout).

## sample

2
3 3
0 1 4
1 2 3
0 2 5
4 4
0 1 10
1 2 20
2 3 30
3 0 40

4
30

</p>