CSES - Datatähti 2016 alku - Lennot
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi on tällä hetkellä Syrjälässä ja haluaa matkustaa Lehmälään. Tiedossasi on lentoyhteydet eri kaupunkien välillä.

Lentoyhtiö antoi Uoleville erikoisen tarjouksen: hän saa valita minkä tahansa lentoreitin ja joka toinen lento reitillä on ilmainen. Ilmaisia ovat reitin 2., 4., 6. jne. lento. Mikä on halvin hinta, jolla Uolevi pääsee perille?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja mm: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n. Kaupunki 1 on Syrjälä ja kaupunki nn on Lehmälä.

Tämän jälkeen syötteessä on mm riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kolme kokonaislukua aa, bb ja hh. Tämä tarkoittaa, että lento lähtee kaupungista aa, päätyy kaupunkiin bb ja sen hinta on hh.

Jokainen syötteessä kuvattu lento on yksisuuntainen. On mahdollista, että kaupungista toiseen on saatavilla useita lentoja, mutta lento päätyy aina eri kaupunkiin kuin mistä se lähtee.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: halvin hinta, jolla Uolevi pääsee lentämään Syrjälästä Lehmälään.

Voit olettaa, että on olemassa ainakin yksi lentoreitti.

Esimerkki

Syöte:

4 6
1 2 5
2 3 8
2 1 4
3 1 6
3 4 1
4 2 3

Tuloste:

6

Selitys: Uolevin lentoreitti on 12341 \rightarrow 2 \rightarrow 3 \rightarrow 4. Kustannus on 5+0+1=65+0+1=6.

Rajat

Kaikissa osatehtävissä pätee:

  • 1a,bn1 \le a, b \le n
  • 1h1091 \le h \le 10^9

Osatehtävä 1 (24 pistettä)

  • 2n102 \le n \le 10
  • 1m201 \le m \le 20

Osatehtävä 2 (37 pistettä)

  • 2n10002 \le n \le 1000
  • 1m20001 \le m \le 2000

Osatehtävä 3 (39 pistettä)

  • 2n1052 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5