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 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 Metsälä.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kolme kokonaislukua aa, bb ja cc: lento alkaa kaupungista aa, päättyy kaupunkiin bb ja sen hinta on cc. 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 xx, sen hinnaksi tulee x/2\lfloor x/2 \rfloor (pyöristys alaspäin kokonaisluvuksi).

Rajat

  • 2n1052 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \le c \le 10^9

Esimerkki

Syöte:

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

Tuloste:

2