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

• 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:

4 5
1 2 2
2 4 3
2 1 1
1 3 5
3 4 2

Tuloste:

5 7 8