Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Pigulia

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

Приклад

 

Пояснення до прикладу.

 Тут є 2 маршрути з 1 в 3.

 1-3 та 1-2-3.  Небезпека першого рівна 2, другого - 1

Введення

Виведення

3

3

 

1

2

1

2

3

1

1

3

2

       1

 

дміністрації обрати самий безпечний маршрут для президента (тобто такий, небезпека якого мінімально можлива). Будь які  два міста можуть бути з’єднані кількома дорогами.

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


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"