Firma TOL produce bunuri de larg consum; are o fabrica in resedinta judetului care este localitatea numerotata $1$ si $n-1$ magazine, cate unul in fiecare dintre celelalte $n-1$ localitati din judet. Pentru a transporta produsele de la fabrica la cele $n-1$ magazine, TOL are la dispozitie $p$ camioane. Deoarece produsele fabricii nu sunt voluminoase si nici nu cantaresc prea mult, capacitatea camioanelor este practic nelimitata, astfel incat orice camion ar putea aproviziona intr-o singura cursa toate magazinele din judet. O cursa a unui camion incepe obligatoriu la fabrica (adica in localitatea $1$), poate trece de mai multe ori printr-o localitate si se poate termina in oricare localitate a judetului; nu este obligatoriu ca din cursa camionul sa revina la localitatea 1.

Costul unei astfel de curse este direct proportional cu distanta parcursa. Camioanele fiind cam vechi, ele nu pot efectua decat o singura cursa (indiferent de lungimea acesteia).

Costul unei astfel de curse este direct proportional cu distanta parcursa. Camioanele fiind cam vechi, ele nu pot efectua decat o singura  cursa (indiferent de lungimea acesteia).

Programatorul firmei TOL primeste ca sarcina de serviciu elaborarea unei planificari care sa stabileasca traseele a cel mult $p$ curse prin care sa fie aprovizionate toate localitatile judetului, iar suma distantelor parcurse de camioane in aceste curse sa fie minima. El nu se prea descurca cu programarea, dar e bine informat si stie ca lotul naţional de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.

Programatorul firmei TOL primeste ca sarcina de serviciu elaborarea unei planificari care sa stabileasca traseele a cel mult $p$ curse prin care sa fie aprovizionate toate localitatile judetului, iar suma distantelor parcurse de camioane in aceste curse sa fie minima. El nu se prea descurca cu programarea, dar e bine informat si stie ca lotul national de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.
h2. Cerinta
 
Scrieti un program care determina o planificare a traseelor pentru cel mult p curse astfel incat prin aceste curse sa fie aprovizionate toate cele $n-1$ magazine, iar suma distantelor parcurse de camioanele plecate in aceste curse sa fie minima.

h2. Date de intrare

Fisierul de intrare $camion2.in$ ...

Fisierul de intrare $camion2.in$ contine:
 
* pe prima linie doua valori numerice naturale pozitive $n$ si $p$ cu semnificatia din enunt;
* pe fiecare dintre urmatoarele $n-1$ linii, $3$ valori numerice naturale pozitive $v1$, $v2$, $d$ (v1 ≠ v2) separate printr-un spatiu, cu semnificatia: intre localitatile $v1$ si $v2$ este un drum direct de lungime $d$.
 

h2. Date de iesire

In fisierul de iesire $camion2.out$ ...

Fisierul de iesire $camion2.out$ va contine o singura linie care va contine suma distantelor parcurse de camioane.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $n$ ≤ $1000$ ; pentru $15%$ din teste $n$ ≤ $20$
* $p$ ≤ $25$
* Nu exista doua localitati intre care sa existe doua drumuri directe.
* Lungimea unui drum direct nu depaseste $100$ si este un numar nenul.
 

h2. Exemplu
table(example). |_. camion2.in |_. camion2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 1
  1 2 10
  3 1 7
  4 3 1
  3 5 2
| 30
|
| 5 3
  1 2 10
  3 1 7
  4 3 1
  3 5 2
| 21

|

h3. Explicatie

h2. Explicatie

...

# Se foloseste un singur camion. Cursa are urmatorul traseu: {$1-3-4-3-5-3-1-2$}.
Suma distantelor este: {$7+1+1+2+2+7+10=30$}
# Se folosesc doua camioane. Cele doua curse sunt: {$1-3-4-3-5$} si {$1-2$}.
Suma distantelor este: {$7+1+1+2+10=21$}

== include(page="template/taskfooter" task_id="camion2") ==

3130