Students celebrate today! In one of the new buildings of the university, they decided to open a canteen. For these purposes, you need to choose one of the buildings in which the dining room will be located. In order for students to be distracted from their studies as little as possible, it was decided to choose a building so that the maximum distance from it to all other buildings was as small as possible.
Help find such a building!
Input
The first line contains two numbers N and M - the number of buildings and the number of roads connecting the buildings (1<=N<=100, 0 <=M<=(N(N−1))/2. Further in M lines are located road descriptions: 3 integers s
i, e
i, l
i - buildings where the road starts and ends and the length of the road, respectively (1< ;=s
i, e
i<=N, 0<=l
i,=100, roads are bidirectional).
Output
It is necessary to display one number - the number of the desired building. If there are several buildings that meet the criteria, select the building with the lowest number among them.
|
Enter |
Output |
|
3 2
|
2 |
|
3 1
1 2 10
|
1 |