When you want to get quick to some place in the city you don't often look for the shortest distance to there. Sometimes what is important is how width the street is. We will say that a route in the city had width is the width of the smallest street you will have to pass through. Now you are give the city network of streets and intersections and the width of each street and you are asked to provide the width of the widest path between intersection with number 1 and intersection with number N.

Input

On the first line of the input you will find two integers N (2 < N < 10000) the number of intersections in the city and M (1 < M < 100000) the number of streets in the city. On each of the next M lines you will get information about one street in the form of 3 integers I, J, W (1 < W < 65000) which will mean that intersections I and J are connected via street with width W.

Output

A single integer representing the width of the path between 1 and N with maximum width. If no path exists between 1 and N output 0

Example

Input:
5 6
1 2 1
1 3 3
1 4 9
2 5 10
3 5 4
4 5 2

Output:
3