CSES - Teleportit II
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Pelaat peliä, jossa on nn tasoa ja niiden välillä mm teleporttia. Jokaiseen teleporttiin liittyy tietty hinta.

Tehtäväsi on päästä tasolta 11 tasolle nn tasan kk teleportin kautta. Mikä on halvin kokonaishinta tähän?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja kk: tasojen määrä, teleporttien määrä ja askelten määrä. Tasot on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden teleportin. Rivillä on kolme kokonaislukua aa, bb ja cc: teleportti vie tasolta aa tasolle bb ja sen hinta on cc.

Tuloste

Tulosta halvin mahdollinen reitin hinta. Voit olettaa, että ainakin yksi reitti on olemassa.

Rajat

  • 1n1001 \le n \le 100
  • 1mn(n1)1 \le m \le n(n-1)
  • 1k1091 \le k \le 10^9
  • 1a,bn1 \le a,b \le n
  • 1c1091 \le c \le 10^9

Esimerkki

Syöte:

3 4 8
1 2 5
2 3 4
3 1 1
3 2 2

Tuloste:

27