Fişierul intrare/ieşire:	ktree.in, ktree.out	Sursă	All You Can Code 2008
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.025 sec	Limită de memorie	80000 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Ktree

Miruna a ajuns in Tara Minunilor. Acest taram fermecat este alcatuit din N orase legate intre ele prin N-1 drumuri astfel incat din orice oras se poate ajunge in oricare altul folosind reteaua de drumuri existenta. Deoarece s-a saturat sa fie tratata ca o printesa cuminte, Miruna vrea sa detoneze exact M drumuri. Unele drumuri sunt construite mai bine decat altele, de aceea Miruna are nevoie de mai mult explozibil pentru a-si atinge obiectivul malefic. Pentru fiecare drum se cunoaste pretul care trebuie platit pentru a achizitiona explozibilul necesar detonarii lui. Dupa ce drumurile alese vor fi distruse, Miruna doreste totusi sa poate circurla pornind din orasul 1 in exact K orase folosind ceea ce a ramas din reteaua stradala pentru a putea jefui negustorii veniti de peste mari si tari.
Ajutati-o pe fetita ajunsa in Tara Minunilor sa cheltuie cat mai putin!

Date de intrare

Pe prima linie a fisierului de intrare ktree.in se vor afla 3 numere intregi N, M, si K avand semnificatia din enunt. Pe urmatoarele N-1 linii se vor afla cate 3 numere A, B, C, semnificand faptul ca intre orasul A si orasul B exista un drum bidirectional pentru care costul detonarii este C.

Date de iesire

Fisierul ktree.out va contine un singur numar intreg reprezentand costul minim cerut sau -1 in caz ca nu exista solutie.

Restrictii si precizari

• 1 < N < 75
• 1 ≤ M < N
• 1 ≤ K < N
• Costurile drumurilor vor fi mai mici decat 1000.

Exemple

Explicatie

In primul exemplu Miruna va detona singurul drum, care are costul 3. In al doilea exemplu, va distruge drumurile dintre urmatoarele perechi de orase: (2, 7), (3, 5), (3, 6), (1, 4).

Cum se trimit solutii?