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

Poveste şi cerinţă...

Ne aflăm în anul $2050$, iar metroul din Drumul Taberei a fost inaugurat recent. Firmele de Taxi consideră că viaţa bucureştenilor a devenit acum prea bună, aşa că au hotărât să-i pedepsească mărind costurile unei călătorii cu taxi-ul. Mai exact, un client care face o comandă telefonică trebuie acum să plătească taxi-ul şi pentru distanţa pe care acesta o parcurge de la locaţia sa iniţială până la adresa clientului. Mai mult, dacă la un moment dat există $M$ comenzi telefonice care trebuie satisfăcute şi $M$ taximetrişti liberi, dispeceratul va cupla taximetriştii cu comenzile astfel încât distanţa totală parcursă de către cei $M$ taximetrişti până la adresele corespunzătoare să fie maximă. Noi dorim să studiem costurile unui asemenea cuplaj, în funcţie de poziţiile iniţiale ale taximetriştilor şi ale clienţilor.
 
Bucureştiul a devenit între timp un arbore neorientat cu $N$ noduri şi distanţe pozitive pe muchii (o transformare tragică, dar care nu a înrăutăţit neaparat traficul). Fiecare dintre cei $M$ taximetrişti se poate afla în oricare din cele $N$ noduri. Acelaşi lucru este valabil pentru fiecare dintre cei $M$ clienţi. Un nod poate găzdui un număr nelimitat de taximetrişti şi/sau clienţi. Astfel, există în total $N^2M^$ configuraţii diferite ale poziţiilor taxi/client. Dacă un taximetrist care se află în nodul $X$ este cuplat cu o comandă din nodul $Y$, costul călătoriei sale va fi egal cu distanţa dintre nodurile $X$ şi $Y$. Întrebarea noastră este următoarea: Dacă $S$ ar fi suma cuplajelor de cost maxim pentru toate cele $N^2M^$ configuraţii posibile, ce valoare ar avea $S *modulo* 10^9^ + 7$?

h2. Date de intrare

Fişierul de intrare $taxi2.in$ ...

Fişierul de intrare $taxi2.in$ va conţine pe prima sa linie numerele $N$ şi $M$, semnificând numărul de noduri ale Bucureştiului, respectiv numărul de taxi-uri şi numărul de clienţi. Următoarele $N - 1$ linii vor conţine un triplet $a b dist$ cu semnificaţia că există o muchie neorientată între nodurile $a$ şi $b$ de distanţă $dist$.

h2. Date de ieşire

În fişierul de ieşire $taxi2.out$ ...

În fişierul de ieşire $taxi2.out$ se va afla valoarea $S *modulo* 10^9^ + 7$.

h2. Restricţii

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

* $1 ≤ N, M ≤ 1.000$
* Pentru $70%$ din punctaj, $1 ≤ N, M ≤ 100$
* Pentru fiecare muchie a arborelui, $1 ≤ dist ≤ 10.000$

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

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

| 2 1
1 2 5
| 10

|

h3. Explicaţie

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

...

h2. Explicaţie

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

Există $2^2^ = 4$ configuraţii. În 2 din ele taxi-ul şi clientul se află în acelaşi nod, deci costul e 0. În celelalte 2 se află în noduri diferite deci costul e 5.