Dangerous route

In one country there are n cities, some of which are connected by two-way routes. Cities are numbered by integers from 1 to n. In times of financial crisis the level of the crime in a state rose and the crime groups are organized. The most dangerous of these was "Timur and his gang" led by a notorious criminal circles by Timur, that commit robberies on most of the roads. As a result, some roads became dangerous to drive.

Baha must get out of city 1 and go to city n. Since he appreciate his life too much (and his wallet also), he decided to cheat Timur and go to destination by the least dangerous route, even if it is not the shortest. Baha defined the level of the danger for each road as an integer from 0 (safe) to 106 (very dangerous). The danger of the route is the maximum value among the dangers of the roads that make up this route.

Help him to choose the safest route (one which has the minimum possible risk).


First line contains two integers n and m (2n, m106). Each of the next m lines defines one road and contains three integers:

  • a, b (1a, bn) - cities, connected with the road;
  • c (0c106) - the danger of the road.

Any two cities can be connected by several roads.


One integer - the danger of the most safe route.


Time limit 4 seconds
Memory limit 128 MiB
Input example #1
3 2
1 2 1
2 3 1
Output example #1
Input example #2
6 7
1 2 1
2 3 2
3 4 3
4 6 5
2 6 10
2 5 7
5 6 1

Output example #2