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.