G :: IUST Problem G

Time Limit: 2 Seconds    Memory Limit: 32768 KB

A clever police lives in a city with n segments. These n segments are connected with a number of streets. A terrorist group in all segments of the city is playing. They are constantly changing their segment. A terrorist locating in the segment i, who wants to go to segment j, chooses the shortest path between segments i and j. Our clever police desires to write a program to find a segment with the maximum traffic of terrorists movements.

Input

The first line of the input contains one integer n, which indicates the number of test cases. For each test case, the next two lines show v (the number of segments) and e (the number of streets between segments) respectively. The e following lines contain three numbers: departure segment, destination 

segment, and the length of the street between the departure and the destination segments.

Output

The index of a segment, where the police must be located (the segment with the maximum traffic of terrorists).

Sample Input

1
7
9
0 2 3
0 3 2
0 5 1
1 6 18
2 4 3
3 6 17
4 6 15
4 5 3
6 5 14

Sample Output

6

Submit

Source: 12th Iran Nationwide Internet Contest II