Uolevi ja Maija ovat automatkalla Euroopassa, ja he haluaisivat ajaa tietystä kaupungista toiseen. Ongelmana on kuitenkin, että monilla teillä on käytössä tietulli.

Voisitko suunnitella heille reitin, jonka varrella on mahdollisimman vähän tietulleja?

Syöte

Syötteen alussa on kaksi kokonaislukua n ja m: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n. Uolevi ja Maija ovat aluksi kaupungissa 1, ja he haluaisivat päästä kaupunkiin n.

Tämän jälkeen syötteessä on m riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua a_i, b_i ja t_i. Tämä tarkoittaa, että kaupungista a_i on tie kaupunkiin b_i. Viimeinen arvo t_i on joko 0 (ei tietullia) tai 1 (tietulli). Kaikki tiet ovat kaksisuuntaisia.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako tietullia Uolevi ja Maija joutuvat maksamaan, jos he valitsevat parhaan reitin.

Rajat

• 2 \le n \le 5\cdot 10^4
• 1 \le m \le 10^5
• 1 \le a, b \le n

Voit olettaa, että verkko on yhtenäinen.

Esimerkki

Syöte:

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

Tuloste:

1

Optimireitillä 1, 2, 4, 3, 6 on yksi tietulli, osuudella 3..5.