CSES - Lentomatka
  • Time limit: 2.00 s
  • Memory limit: 128 MB

Uolevin kummitäti asuu Vladivostokissa, ja hiihtoloman aikaan Uolevi päätti lähteä käymään tädin luona. Uolevi itse asuu Helsingissä.

Tiedossasi on lentoasemat ja niiden väliset lennot sekä kunkin lennon hinta. Lisäksi Uolevilla on yksi alennuskuponki, jonka avulla hän voi matkustaa puoleen hintaan minkä tahansa reitin varrella olevan lennon.

Mikä on halvin hinta matkalle Helsingistä Vladivostokiin?

Syöte

Syötteen alussa on kaksi kokonaislukua nn ja mm: kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n. Kaupunki 1 on Helsinki ja kaupunki nn on Vladivostok.

Tämän jälkeen syötteessä on mm riviä, joista jokainen kuvaa yhden lennon. Rivillä on kolme kokonaislukua aia_i, bib_i ja hih_i: mistä kaupungista lento alkaa, mihin kaupunkiin lento päättyy ja mikä on sen hinta. Kaikki lennot ovat yksisuuntaisia.

Jos lennon hinta on xx, niin sen alennettu hinta on x/2\lfloor x/2 \rfloor eli x/2x/2 pyöristettynä alaspäin kokonaisluvuksi.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: halvin hinta matkalle.

Voit olettaa, että jokin reitti on varmasti olemassa.

Rajat

  • 1n51041 \le n \le 5 \cdot 10^4
  • 1m1051 \le m \le 10^5
  • 1ai,bin1 \le a_i, b_i \le n
  • aibia_i \neq b_i
  • 1hi1091 \le h_i \le 10^9

Esimerkki

Syöte:

4 5
1 2 6
2 3 6
3 4 2
1 3 14
4 3 3

Tuloste:

9

Selitys: Uolevi lentää ensin 1->3 käyttäen alennuskupongin (hinta 7). Tämän jälkeen hän lentää 3->4 (hinta 2). Yhteishinta on siis 9.