e-olymp
Yarışlar

Spanning Tree + DSU

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

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

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

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

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

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

a, b - города, соединенные дорогой (1a, bn);

c - опасность дороги (0c1000000).

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 2
1 2 1
2 3 1
Çıxış verilənləri #1
1