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

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

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

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

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

• a, b - города, соединенные дорогой (1 ≤ a, b ≤ n);
• c - опасность дороги (0 ≤ c ≤ 106).

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

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

Одно целое число - опасность самого безопасного маршрута.