Небезпечний маршрут
Небезпечний маршрут
У певній країні є 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) — небезпечність дороги.
Будь-які два міста можуть бути з'єднані кількома дорогами.
Вихідні дані
Виведіть одне ціле число — небезпечність найбезпечнішого маршруту.
Приклад
3 2 1 2 1 2 3 1
1
6 7 1 2 1 2 3 2 3 4 3 4 6 5 2 6 10 2 5 7 5 6 1
5