Tehtäväsi on etsiä halvin lentoreitti Syrjälästä Metsälään. Erikoisuutena sinulla on käytössä alennuskuponki, jolla saat puolitettua minkä tahansa reitillä olevan lennon hinnan. Voit kuitenkin puolittaa vain yhden lennon hinnan.

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ä Syrjälästä Metsälään on ainakin yksi reitti.

Tuloste

Tulosta yksi kokonaisluku: halvin reitti Syrjälästä Metsälään.

Kun käytät alennuskupongin lentoon, jonka hinta on x, sen hinnaksi tulee \lfloor x/2 \rfloor (pyöristys alaspäin kokonaisluvuksi).

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:

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

Tuloste:

2