Dangerous route#325
In a certain country, there are cities, some of which are connected by two-way roads. The cities are numbered from to . During a financial crisis, crime rates increased, and organized criminal groups appeared. As a result, traveling on some roads became dangerous.
Baha needs to travel from city to city . Since he values his life (and his wallet), he decides to outsmart the robbers and choose the safest route, even if it is not the shortest possible. For each road, he assigns a danger level, represented by an integer from (safe) to 10^6 (very dangerous). The danger of a route is the maximum danger among the roads in the route.
Help him find the safest possible route (that is, a route whose maximum danger is as small as possible).
The first line contains two integers and (2 \le n, m \le 10^6). Each of the next lines describes one road and contains three integers:
, (1 \le a, b \le n) — the cities connected by the road;
(0 \le c \le 10^6) — the danger of the road.
There may be multiple roads between any two cities.
Print one integer — the minimum possible danger of the safest route.
Example 1
Example 2