У певній країні є $n$ міст, деякі з яких сполучені двосторонніми дорогами. Міста пронумеровані цілими числами від $1$ до $n$. Під час фінансової кризи рівень злочинності в державі підвищився, і з`явилися організовані злочинні групи. Внаслідок цього деякі дороги стали небезпечними для подорожей. Басі потрібно потрапити з міста $1$ у місто $n$. Оскільки він дуже цінує своє життя (і гаманець), він вирішив обманути грабіжників і обрати найменш небезпечний маршрут, навіть якщо він не буде найкоротшим. Для кожної дороги він визначив її небезпеку, як ціле число від $0$ (безпечна) до $10^6$ (дуже небезпечна). Небезпека маршруту --- це максимум серед небезпек доріг, які складають маршрут. Допоможіть йому вибрати найбезпечніший маршрут (тобто той, небезпека якого мінімально можлива). \InputFile Перший рядок містить два цілих числа: $n$ та $m~(2 \le n, m \le 10^6)$. Кожен з наступних $m$ рядків визначає одну дорогу і містить три цілих числа: \begin{itemize} \item $a, b~(1 \le a, b \le n)$ --- міста, з`єднані дорогою; \item $c~(0 \le c \le 10^6)$ --- небезпечність дороги. \end{itemize} Будь-які два міста можуть бути з'єднані кількома дорогами. \OutputFile Виведіть одне ціле число --- небезпечність найбезпечнішого маршруту. \includegraphics{https://static.e-olymp.com/content/e3/e38592c669b2f7e2841ee8faf0346f49e807fccb.gif}