CSES - Lentoreitti
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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 nn ja mm: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n. Syrjälän numero on 1, ja Lehmälän numero on nn.

Sitten syötteessä on mm riviä, jotka kuvaavat lennot. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: kaupungista aa on lento kaupunkiin bb hintaan cc. Kaikki lennot ovat yksisuuntaisia.

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

Tuloste

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

Rajat

  • 2n1052 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \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