Cerința

Porumbeii au pornit un război crâncen împotriva ciorilor, dar ele au construit garduri defensive pe toate rutele pe care le-ar putea folosi armata porumbeilor pentru a le ataca cetatea. Pentru a ajunge la cetatea ciorilor armata trebuie sa treacă de gardurile construite de ciori.
Pentru că porumbeii obosesc din cauza zborului ei trebuie sa se odihneasca pe statui, astfel armata poate merge doar pe drumurile cunoscute dintre două statui. Există n statui, iar armata se află inițial pe statuia cu numărul 1, iar cetatea ciorilor se va afla pe cea cu numărul n.
Armata porumbeilor deține un cioc bionic de putere K. Acesta poate sparge garduri cu rezistență mai mica sau egala cu K, armata putând astfel să treacă pe acel drum.
Generalul armatei porumbeilor vă cere să găsiți puterea minimă pe care o poate avea ciocul bionic pentru ca armata să poată ajunge la cetatea ciorilor.

Date de intrare

Fișierul de intrare Ohoo.in va conține: Pe prima linie numărul natural n reprezentând numărul de statui și numărul natural m reprezentând numărul de drumuri existente între statui. Pe următoarele m linii se vor găsi câte 3 numere: x, y, r, cu semnificația că există un drum bidirecțional între statuile x și y blocat de un gard de rezistență r.

Date de ieșire

Fișierul de ieșire Ohoo.out va conține un singur număr natural K, reprezentând puterea minimă pe care o poate avea ciocul bionic astfel încât armata să poată ajunge la cetatea ciorilor.

Restricții și precizări:

• 2 ≤ n ≤ 100.000
• 1 ≤ m ≤ 250.000
• Rezistențele gardurilor sunt numere naturale nenule și nu depășesc 1.000.000
• Între două statui pot exista mai multe drumuri cu garduri de rezistențe diferite
• Întotdeauna există soluție
• Pentru 60% din teste n ≤ 1000 și K ≤ 1000
• Se acordă 10 puncte pentru exemplu
• Atenție la numele fișirelor de intrare și de ieșire!

Exemplu:

Ohoo.in

5 6
1 2 3
1 4 1
2 3 2
3 5 3
4 5 4
3 4 4

Ohoo.out

3

Explicație

Alegem drumul 1-2-3-5 folosind o putere maximă de 3.