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