camion

Î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 camion.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 \neq v2)$ se-parate 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 camion.out va conţine o singură linie care va conţine suma distanţelor parcurse camioane.

Restricţii şi precizări

• $n \leq 1 \ 000$; pentru $15 \%$ din teste $n \leq 20$
• $p \leq 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.

Exemplul 1

camion.in

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

camion.out

30

Explicație

Se foloseşte un singur camion; cursa are următorul traseu: $1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 2$
Suma distanţelor este: $7+1+1+2+2+7+10=30$

Exemplul 2

camion.in

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

camion.out

21

Explicație

Se folosesc două camioane; cele două curse sunt: $1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 5$ şi $1 \rightarrow 2$.
Suma distanţelor este: $7+1+1+2+10=21$