eolymp
Задачи

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

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

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

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

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

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

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

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

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

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

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

prb325.gif

Лимит времени 4 секунды
Лимит использования памяти 128 MiB
Входные данные #1
3 2
1 2 1
2 3 1
Выходные данные #1
1
Входные данные #2
6 7
1 2 1
2 3 2
3 4 3
4 6 5
2 6 10
2 5 7
5 6 1

Выходные данные #2
5