Uolevi on tällä hetkellä Syrjälässä ja haluaa matkustaa Lehmälään. Tiedossasi on lentoyhteydet eri kaupunkien välillä.

Lentoyhtiö antoi Uoleville erikoisen tarjouksen: hän saa valita minkä tahansa lentoreitin ja joka toinen lento reitillä on ilmainen. Ilmaisia ovat reitin 2., 4., 6. jne. lento. Mikä on halvin hinta, jolla Uolevi pääsee perille?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu 1,2,\ldots,n. Kaupunki 1 on Syrjälä ja kaupunki n on Lehmälä.

Tämän jälkeen syötteessä on m riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kolme kokonaislukua a, b ja h. Tämä tarkoittaa, että lento lähtee kaupungista a, päätyy kaupunkiin b ja sen hinta on h.

Jokainen syötteessä kuvattu lento on yksisuuntainen. On mahdollista, että kaupungista toiseen on saatavilla useita lentoja, mutta lento päätyy aina eri kaupunkiin kuin mistä se lähtee.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: halvin hinta, jolla Uolevi pääsee lentämään Syrjälästä Lehmälään.

Voit olettaa, että on olemassa ainakin yksi lentoreitti.

Esimerkki

Syöte:

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

Tuloste:

6

Selitys: Uolevin lentoreitti on 1 \rightarrow 2 \rightarrow 3 \rightarrow 4. Kustannus on 5+0+1=6.

Rajat

Kaikissa osatehtävissä pätee:

• 1 \le a, b \le n
• 1 \le h \le 10^9

Osatehtävä 1 (24 pistettä)

• 2 \le n \le 10
• 1 \le m \le 20

Osatehtävä 2 (37 pistettä)

• 2 \le n \le 1000
• 1 \le m \le 2000

Osatehtävä 3 (39 pistettä)

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5