În judeţul Alba sunt n localităţi numerotate de la 1 la n. Între aceste localităţi există o reţea de drumuri cu dublu sens (bidirecţionale) concepută astfel încât între oricare două localităţi există un singur drum care, fie e direct, fie trece prin alte localităţi. Există n-1 perechi de localităţi cu proprietatea că între localităţile ce formează o pereche există un drum direct. Lungimea acestor drumuri directe este cunoscută.
Firma TOL produce bunuri de larg consum; are o fabrică în reşedinţa judeţului care este localitatea numerotată 1 şi n-1 magazine, câte unul în fiecare dintre celelalte n-1 localităţi din judeţ. Pentru a transporta produsele de la fabrică la cele n-1 magazine, TOL are la dispoziţie p camioane. Deoarece produsele fabricii nu sunt voluminoase şi nici nu cântăresc prea mult, capacitatea camioanelor este practic nelimitată, astfel încât orice camion ar putea aproviziona într-o singură cursă toate magazinele din judeţ. O cursă a unui camion începe obligatoriu la fabrică (adică în localitatea 1), poate trece de mai multe ori printr-o localitate şi se poate termina în oricare localitate a judeţului; nu este obligatoriu ca din cursă camionul să revină la localitatea 1.
Costul unei astfel de curse este direct proporţional cu distanţa parcursă. Camioanele fiind cam vechi, ele nu pot efectua decât o singură cursă (indiferent de lungimea acesteia).
Programatorul firmei TOL primeşte ca sarcină de serviciu elaborarea unei planificări care să stabilească traseele a cel mult p curse prin care să fie aprovizionate toate localităţile judeţului, iar suma distanţelor parcurse de camioane în aceste curse să fie minimă. El nu se prea descurcă cu programarea, dar e bine informat şi ştie că lotul naţional de informatică se află la Alba Iulia. Aşa că apelează la voi pentru a-i rezolva problema.
Cerinţă
Scrieţi un program care determină o planificare a traseelor pentru cel mult p curse astfel încât prin aceste curse să fie aprovizionate toate cele n-1 magazine, iar suma distanţelor parcurse de camioanele plecate în aceste curse să fie minimă.
Date de intrare
Fişierul camion1.in conţine pe prima linie două valori numerice naturale pozitive n şi p cu semnificaţia din enunţ. Pe fiecare dintre următoarele n-1 linii, 3 valori numerice naturale pozitive v1, v2, d (v1 ≠ v2) separate printr-un spaţiu, cu semnificaţia: între localităţile v1 şi v2 este un drum direct de lungime d.
Date de ieşire
Fişierul camion1.out va conţine o singură linie care va conţine suma distanţelor parcurse camioane.
Restricţii
n ≤ 1000
Pentru 15% din teste n ≤ 20
p ≤ 25
Nu există două localităţi între care să existe două drumuri directe.
Lungimea unui drum direct nu depăşeşte 100 şi este un număr nenul.
Exemple
camion1.in
camion1.out
Explicaţii
5 1
1 2 10
3 1 7
4 3 1
3 5 2
30
Se foloseşte un singur camion; cursa are următorul traseu: 1-3-4-3-5-3-1-2
Suma distanţelor este: 7+1+1+2+2+7+10=30
5 3
1 2 10
3 1 7
4 3 1
3 5 2
21
Se folosesc două camioane; cele două curse sunt: 1-3-4-3-5 şi 1-2.
Suma distanţelor este: 7+1+1+2+10=21