Uolevi haluaa matkustaa Syrjälästä Lehmälään lentäen niin, että reitin kokonaishinta on mahdollisimman halpa. Sinulle on annettu tiedot kaupungeista ja niiden välisistä lennoista. Mitkä kaupungit ovat varmasti halvimman reitin varrella?

Syöte

Syötteessä on ensin kaksi kokonaislukua n ja m: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu 1,2,\ldots,n. Syrjälän numero on 1, ja Lehmälän numero on n.

Sitten syötteessä on m riviä, jotka kuvaavat lennot. Jokaisella rivillä on kolme kokonaislukua a, b ja c: kaupungista a on lento kaupunkiin b hintaan c. Kaikki lennot ovat yksisuuntaisia.

Voit olettaa, että on olemassa jokin reitti Syrjälästä Lehmälään.

Tuloste

Tulosta ensin kokonaisluku k: montako kaupunkia on varmasti lentoreitin varrella. Tulosta sitten k kaupunkia järjestyksessä numeron mukaan.

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

4
1 3 4 5