У деякій країні є n міст, деякі з яких зєднані двохсторонніми дорогами. Міста пронумеровані цілими числами від **1** до **n**. У період фінансової кризи рівень злочинності у країні зріс і почали зявлятися організовані злочинні угрупування. Найнебезпечнішою з них стала "Тимур та його шайка", очолювана досить відомим у кримінальних колах Тімою, яка почала розбійничати на більшості доріг. В результаті по деяким дорогам стало небезпечно їздити.

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

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

Вхідні дані

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

a, b (1 ≤ a, b ≤ n) - міста, з`єднані дорогою; c (0 ≤ c ≤ 1000000) - небезпечність дороги.

Довільні два міста можуть бути з`єднані декількома дорогами. Числа у рядках відокремлені пропусками.

Вихідні дані

Одне ціле число - небезпечність самого безпечного маршруту.