bee 2182 - Luciano and the Bike

Luciano is a fan of sports, even more when it comes to cycling. Luciano has a bicycle and takes care as if it were his child, avoiding the maximum to walk in bad streets, that is, streets with a lot of holes. Luciano gonna change city and needs your help to find the best district to live in.

For Luciano, the best district is the one where the average number of holes between all paths of the district is the smallest possible. Two houses are in the same district if it is possible to leave from one and reach the other using the existing paths. After deciding which district to live, Luciano chooses the house based on his identifier, he prefers the house with the largest possible identifier.

You will receive a list with N houses available for Luciano live and M paths between these houses. In each of these paths there is an amount of holes. There will never be more than one direct path between two houses. Each house has an identifier [1, N].

If there is a district with only one house, the amount of holes in this district will be 0, since there is no path.

Help Luciano and tell him the identifier of the house where he should live in.

Input

The first line contains two integers N, M, indicating, respectively, the number of available house and the number of paths between. (1 ≤ N ≤ 10⁴, 0 ≤ M ≤ 10⁵).

Then M lines follows, containing three integers X, Y, B, indicating that there is a bidirectional connection between the houses X and Y containing B holes. (1 ≤ X, Y ≤ N, X ≠ Y, 0 ≤ B ≤ 100).

Output

Print a single line, the identifier of the house where Luciano should live in.

Input Samples	Output Samples
5 4 1 2 5 2 3 15 4 5 9 1 3 3	3

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

5 7
2 4 3

1 2 2

1 3 4

2 3 5

5 4 8

2 5 3

5 3 4