Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Halvimmat

Halvimmat


View task | Model solution | Statistics


Halvimmat

Time limit:1.00 s
Memory limit:128 MB

Tehtäväsi on etsiä kolme halvinta lentoreittiä Syrjälästä Metsälään. Lentoreitti saa kulkea saman kaupungin kautta monta kertaa.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu $1,2,\ldots,n$. Kaupunki 1 on Syrjälä, ja kaupunki $n$ on Metsälä.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$: lento alkaa kaupungista $a$, päättyy kaupunkiin $b$ ja sen hinta on $c$. Jokainen lento on yksisuuntainen.

Tuloste

Tulosta kolme kokonaislukua: kolme halvinta lentoreittiä halvimmasta kalleimpaan.

Voit olettaa, että ainakin kolme erilaista reittiä on olemassa.

Rajat
Esimerkki

Syöte:
4 5
1 2 2
2 4 3
2 1 1
1 3 5
3 4 2


Tuloste:
5 7 8