Syrjälän tietoverkossa on $n$ konetta ja $m$ yhteyttä. Jokainen yhteys kuvaa, miten nopeasti jokin kone voi lähettää tietoa toiselle koneelle.

Kotivalo haluaa ladata tietoa palvelimelta. Mikä on suurin mahdollinen latausnopeus käyttäen verkossa olevia yhteyksiä?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: koneiden ja yhteyksien määrä. Koneet on numeroitu $1,2,\dots,n$ Kone $1$ on palvelin ja kone $n$ on Kotivalon kone.

Tämän jälkeen tulee $m$ riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: kone $a$ voi lähettää tietoa koneelle $b$ nopeudella $c$.

Tuloste

Tulosta yksi kokonaisluku: maksiminopeus, jolla Kotivalo voi ladata tietoa.

Rajat

• $1 \le n \le 500$
• $1 \le m \le 1000$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$

Esimerkki

Syöte:

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

Tuloste:

6