Code Submission Evaluation System Login

Datatähti-valmennus

Alennus


Task | Statistics


CSES - Alennus

Time limit:1.00 s Memory limit:128 MB

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
Esimerkki

Syöte:
3 4
1 2 3
2 3 1
1 3 7
2 1 5


Tuloste:
2