- 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 ja : kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu . Syrjälän numero on 1, ja Lehmälän numero on .
Sitten syötteessä on riviä, jotka kuvaavat lennot. Jokaisella rivillä on kolme kokonaislukua , ja : kaupungista on lento kaupunkiin hintaan . Kaikki lennot ovat yksisuuntaisia.
Voit olettaa, että on olemassa jokin reitti Syrjälästä Lehmälään.
Tuloste
Tulosta ensin kokonaisluku : montako kaupunkia on varmasti lentoreitin varrella. Tulosta sitten kaupunkia järjestyksessä numeron mukaan.
Rajat
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