Code Submission Evaluation System Login

Datatähti-valmennus

Halvimmat


Task | Statistics


CSES - 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.

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

Tuloste

Tulosta kolme kokonaislukua: kolme halvinta lentoreittiä halvimmasta kalleimpaan.

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