Uolevin ja Maijan välinen nettiyhteys on toiminut huonosti viime aikoina. Ennen tarkempia tutkimuksia Uolevi haluaisi selvittää, mikä on teoreettinen suurin nopeus, jolla hän voi lähettää tietoa Maijalle verkossa.

Voisitko auttaa Uolevia laskemaan maksiminopeuden? Huomaa, että tietoa voi kulkea samaan aikaan monta kautta Maijalle.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: verkon koneiden ja yhteyksien määrä. Koneet on numeroitu kokonaisluvuin 1,2,\ldots,n. Kone 1 on Uolevin kone, ja kone n on Maijan kone.

Tämän jälkeen syötteessä on m riviä, joista jokainen kuvaa yhden yhteyden. Rivillä on kolme kokonaislukua a, b ja c. Tämä tarkoittaa, että koneesta a pystyy lähettämään koneeseen b sekunnissa c tavua tietoa.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen nopeus (tavua sekunnissa), jolla Uolevi pystyy lähettämään tietoa Maijalle.

Rajat

• 2 \le n \le 100
• 1 \le m \le 1000
• 1 \le a, b \le n
• 1 \le c \le 10^9

Esimerkki

Syöte:

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

Tuloste:

4