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

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