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

У певній країні є $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)$ — небезпечність дороги.

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

Вихідні дані

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

Приклади