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

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

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

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

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

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

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

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

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