Опасный маршрут

В некотором государстве имеется $n$ городов, некоторые из которых соединены двусторонними дорогами. Города пронумерованы целыми числами от $1$ до $n$. В период финансового кризиса уровень преступности в государстве поднялся и стали появляться организованные преступные группировки. В результате по некоторым дорогам стало опасно ездить.

Бахе надо попасть из города $1$ в город $n$. Так как он слишком ценит свою жизнь (и кошелек), он решил обмануть грабителей и поехать по наименее опасному маршруту, пусть даже он будет не самым коротким. Для каждой дороги он определил ее опасность, как целое число от $0$ (безопасная) до $10^6$ (очень опасная). Опасность маршрута — это максимум из опасностей дорог, составляющих маршрут.

Помогите ему выбрать самый безопасный маршрут (то есть тот, опасность которого минимально возможная).

Входные данные

Первая строка содержит два целых числа $n$ и $m(2\le n,m\le 10^6)$. Каждая из следующих $m$ строк определяет одну дорогу и содержит три целых числа:

• $a,b(1\le a,b\le n)$ — города, соединенные дорогой;

• $c(0\le c\le 10^6)$ — опасность дороги.

Любые два города могут быть соединены несколькими дорогами.

Выходные данные

Выведите одно целое число — опасность самого безопасного маршрута.

Примеры