Задача Pigulia В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой. Дороги пронумеровано целыми числами от 1 до М. Однако в период очередной революции по дорогам стало ездить опасно – революционеры могли и кошелек отобрать… Президент Пигулии решил поехать из столичной резиденции, размещенной а городе 1, в город N с рабочим визитом, но очень боится революционеров. Пигульськая администрация президента определила опасность каждой дороги в виде числа от 0 (безопасная) до 1000 (очень опасная). «Опасность маршрута» - это максимальная из опасностей дорог, входящих в него. Помогите
|
Пример
|
|
|
Пояснения к примеру.
Здесь есть 2 маршрута из 1 в 3: 1-3 и 1-2-3. Опасность первого равна 2, второго - 1
|
|
|
Ввод
|
Вывод
|
|
|
1
|
администрации выбрать самый безопасный маршрут для президента (то есть такой, опасность которого минимально возможна). Любые два города могут соединять несколько дорог.
Технические условия. Программа Pigulia читает с устройства стандартного ввода (клавиатуры) два числа N и M через пробел (2≤ N≤1000, N-1≤ M ≤100000), а далее М строк по 3 целых числа через пробел А,В – города, соединенные дорогой (1≤ А,В ≤ N), и С – «опасность» дороги (0≤ С ≤ 1000). Программа выводит на экран единственное искомое число – «опасность» самого безопасного маршрута.
|
