В некотором государстве имеется $n$ городов, некоторые из которых соединены двусторонними дорогами. Города пронумерованы целыми числами от $1$ до $n$. В период финансового кризиса уровень преступности в государстве поднялся и стали появляться организованные преступные группировки. В результате по некоторым дорогам стало опасно ездить. Бахе надо попасть из города $1$ в город $n$. Так как он слишком ценит свою жизнь (и кошелек), он решил обмануть грабителей и поехать по наименее опасному маршруту, пусть даже он будет не самым коротким. Для каждой дороги он определил ее опасность, как целое число от $0$ (безопасная) до $10^6$ (очень опасная). Опасность маршрута --- это максимум из опасностей дорог, составляющих маршрут. Помогите ему выбрать самый безопасный маршрут (то есть тот, опасность которого минимально возможная). \InputFile Первая строка содержит два целых числа $n$ и $m~(2 \le n, m \le 10^6)$. Каждая из следующих $m$ строк определяет одну дорогу и содержит три целых числа: \begin{itemize} \item $a, b~(1 \le a, b \le n)$ --- города, соединенные дорогой; \item $c~(0 \le c \le 10^6)$ --- опасность дороги. \end{itemize} Любые два города могут быть соединены несколькими дорогами. \OutputFile Выведите одно целое число --- опасность самого безопасного маршрута. \includegraphics{https://static.e-olymp.com/content/e3/e38592c669b2f7e2841ee8faf0346f49e807fccb.gif}