FASTW - Fast Width

no tags 

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

hide comments
Simes: 2020-01-11 15:50:36

Should be in classical

Paul Draper: 2009-03-06 20:01:53

Can two intersections be directly linked by two different roads?


Added by:Nikola P Borisov
Date:2008-12-04
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Bulgarian National Olympiad Round 2 2004 Group A