== include(page="template/taskheader" task_id="berarii") ==

Oamenii beau foarte multa bere in Romania. Pentru fiecare oras $i$ din cele $N$ orase ale tarii (numerotate de la $1$ la $N$) se cunoaste cantitatea de bere $B{~i~}$ ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze $K$ berarii in $K$ orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste $2$ orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras $i$ si o berarie amplasata intr-un oras $X$, care este cea mai apropiata berarie de $X$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, unde $dist(i,X)$ este distanta dintre orasul $i$ si orasul $X$. Compania producatoare de bere doreste sa aleaga amplasarea celor $K$ berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.

Poveste si cerinta...

h2. Date de intrare

Prima linie a fisierului de intrare $berarii.in$ contine numarul intreg $T$, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine $2$ numere intregi: $N$ si $K$. Urmatoarele $N$ linii contin cantitatile de bere cerute in fiecare oras: a $i$-a din aceste linii contine valoarea $B{~i~}$. Urmatoarele $N-1$ linii contin cate $3$ numere intregi: $A$, $B$ si $L$, avand semnificatia ca exista o strada de lungime $L$ intre orasele $A$ si $B$.

...

h2. Date de iesire

Pentru fiecare din cele $T$ teste, in ordinea data in fisierul de intrare, afisati o linie continand valoarea minima posibila pentru costul maxim al transportului berii, in cazul unei amplasari optime a berariilor.

...

h2. Restrictii

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ N$
* $1 ≤ B{~i~} ≤ 10 000$
* Lungimea oricarei strazi este un numar intreg din intervalul $[1, 10 000]$.

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

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

|1
4 2
3
4
2
7
1 2 10
2 3 21
2 4 57
|42

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

|
h3. Explicatie

Arborele este prezentat in figura de mai jos. Orasele in care vor fi construite berarii sunt colorate cu galben. Costul maxim al transportului berii, egal cu 42, se obtine intre orasul $3$ si beraria amplasata in orasul $2$.
 
 

...

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