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