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 n ja m: kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n. Kaupunki 1 on Helsinki ja kaupunki n on Vladivostok.

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

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

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: halvin hinta matkalle.

Voit olettaa, että jokin reitti on varmasti olemassa.

Rajat

• 1 \le n \le 5 \cdot 10^4
• 1 \le m \le 10^5
• 1 \le a_i, b_i \le n
• a_i \neq b_i
• 1 \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.