Dangerous route

In a certain country, there are $n$ cities, some of which are connected by two-way roads. The cities are numbered from $1$ to $n$. During a financial crisis, crime rates soared, and organized criminal groups began to emerge. As a result, traveling along certain roads became dangerous.

Baha needs to travel from city $1$ to city $n$. Since he values both his life and his possessions, he decides to outsmart the robbers by choosing the safest route, even if it's not the shortest. For each road, he has assigned a danger level, represented by an integer between $0$ (completely safe) and $10^6$ (extremely dangerous). The danger of a route is determined by the most dangerous road on that route.

Help him find the safest possible route (i.e., the route with the lowest maximum danger).

Input

The first line contains two integers $n$ and $m(2\le n,m\le 10^6)$. Each of the next $m$ lines describes one road and contains three integers:

• $a,b(1\le a,b\le n)$ — the cities, connected by the road;

• $c(0\le c\le 10^6)$ — the danger of the road.

Multiple roads may exist between any two cities.

Output

Print one integer — the danger of the safest route.

Examples