eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Небезпечний маршрут

Небезпечний маршрут

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

У певній країні є n міст, деякі з яких сполучені двосторонніми дорогами. Міста пронумеровані цілими числами від 1 до n. Під час фінансової кризи рівень злочинності в державі підвищився, і з'явилися організовані злочинні групи. Внаслідок цього деякі дороги стали небезпечними для подорожей.

Басі потрібно потрапити з міста 1 у місто n. Оскільки він дуже цінує своє життя (і гаманець), він вирішив обманути грабіжників і обрати найменш небезпечний маршрут, навіть якщо він не буде найкоротшим. Для кожної дороги він визначив її небезпеку, як ціле число від 0 (безпечна) до 10^6 (дуже небезпечна). Небезпека маршруту — це максимум серед небезпек доріг, які складають маршрут.

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

Вхідні дані

Перший рядок містить два цілих числа: n та m~(2 \le n, m \le 10^6). Кожен з наступних m рядків визначає одну дорогу і містить три цілих числа:

  • a, b~(1 \le a, b \le n) — міста, з'єднані дорогою;

  • c~(0 \le c \le 10^6) — небезпечність дороги.

Будь-які два міста можуть бути з'єднані кількома дорогами.

Вихідні дані

Виведіть одне ціле число — небезпечність найбезпечнішого маршруту.

Приклад

Вхідні дані #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