Given a weighted connected undirected graph with vertices and edges, where the edge weights range from to . The weight of its minimum spanning tree (MST) is defined as the mode of the edge weights. If there are multiple numbers with the same frequency, the mode is considered to be the smallest one. Find the weight of the MST with the minimum possible mode.

Note that there may be duplicate edges or self-loops.

This problem has multiple sets of test data. The first line contains a positive integer , indicating the number of sets of data.

For each set of data:
The first line contains three positive integers .
The next  lines each contain three positive integers , indicating an edge from  to  with weight .

Output one line for each set of data, which is the answer.

3
5 5 3
2 1 1
3 1 2
4 3 3
5 2 2
3 4 3
5 7 3
2 1 3
3 2 2
4 1 1
5 1 2
4 5 3
1 5 3
2 5 1
5 4 3
2 1 3
3 2 3
4 1 3
5 2 2

2
1
3