In some country there are $n$ cities, some of which are connected by two-way roads. The cities are numbered with integers from $1$ to $n$. During the financial crisis, the crime rate in the country rose, and organized criminal groups began to appear. As a result, it became dangerous to travel along certain roads. Baha needs to get from city $1$ to city $n$. Since he values his life (and his wallet) too much, he decided to deceive the robbers and take the least dangerous route, even if it is not the shortest. For each road, he determined its danger as a whole number from $0$ (safe) to $10^6$ (very dangerous). The danger of the route is the maximum of the dangers of the roads that make up the route. Help him choose the safest route (i.e., the one with the minimum possible danger). \InputFile The first line contains two integers $n$ and $m~(2 \le n, m \le 10^6)$. Each of the next $m$ lines defines one road and contains three integers: \begin{itemize} \item $a, b~(1 \le a, b \le n)$ --- cities, connected by the road; \item $c~(0 \le c \le 10^6)$ --- the danger of the road. \end{itemize} Any two cities can be connected by several roads. \OutputFile Print one integer – the danger of the safest route. \includegraphics{https://static.e-olymp.com/content/e3/e38592c669b2f7e2841ee8faf0346f49e807fccb.gif}