Laiko ribojimas: 2s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Greitkeliai

Kruskalijos karalius Konstantinas nori pagerinti kelius savo šalyje. Kruskalijoje yra n miestų, sunumeruotų nuo 1 iki n. Kruskalijos sostinė yra Krustaunas, o jo numeris yra 1. Miestus tarpusavyje jungia m dvikrypčių kelių. Taip pat, iš sostinės įmanoma pasiekti visus kitus miestus.

Kelių gerinimo procedūros metu kai kurie seni keliai bus keičiami naujais greitkeliais. Projekto pabaigoje turi būti įmanoma iš bet kurio miesto patekti į bet kurį kitą miestą važiuojant vien greitkeliais.

Konstantinas nori, kad projektas jam kainuotų kuo mažiau. Be to, jei prie sostinės bus pastatyta daugiau nei d greitkelių, sostinės gyventojai bus nepatenkinti dėl smarkiai padidėjusio triukšmo lygio. Padėkite Konstantinui surasti mažiausią įmanomą kelių atnaujinimo projekto, kuris išpildytų visus reikalavimus ir tenkintų sostinės gyventojus, kainą.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys sveikieji skaičiai n, m ir d (1\\leqd\\leqn\\leq2000,0\\leqm\\leq\\frac{n(n-1)}{2}), reiškiantys Kurskalijos miestų skaičių, kelių skaičių ir didžiausią leistiną greitkelių, esančių šalia sostinės, skaičių.

Toliau seka m eilučių, aprašančių senuosius kelius. Kiekvienoje eilutėje yra po tris sveikuosius skaičius a, b ir c (1\\leqa,b\\leqn,a\\neqb,1\\leqc\\leq10^9), reiškiančius, kad miestus a ir b jungia kelias, kurį paversti greitkeliu kainuoja c. Kiekvieną porą miestų jungia ne daugiau kaip vienas kelias.

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - mažiausią įmanomą projekto kainą. Galite tarti, kad egzistuoja bent vienas būdas išpildyti visus reikalavimus.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 6 2
1 2 2
1 3 1
1 4 2
1 5 1
4 5 10
2 3 4
 
16