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

Poveste şi cerinţă...

Deoarece anul trecut nu ati reusit sa-l ajutati pe Hektor sa treaca bacul, el este nevoit sa-l dea si anul acesta. Vreme trece, vreme vine si s-au apropiat simularile. Anul trecut, Hektor nu a invatat pentru simularea la romana pentru ca a zis atunci ca mult mai este pana la bac si ca are timp destul sa invete (evident, acesta s-a inselat). Tara in care locuieste Hektor are forma unui arbore cu $N$ noduri. Deoarece acesta este un interlop cu relatii internationale, el cunoaste cate o profesoara de romana in fiecare nod al tarii care ii poate da cate un comentariu de invatat pentru simulare. Fiecare comentariu este caracterizat de douna numere $s$ si $e$, $s$ reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar $e$ reprezentand efortul necesar de al toci. Mai sunt fix $M$ zile pana la simulare, iar Hektor isi stie progrmul struna. Pentru fiecare zi $i$ din cele $M$, el are niste afaceri de indeplinit, astfel acesta fiind nevoit sa se deplaseze din nodul $x ~i~$ in nodul $y ~i~$. Deoarece, anul aceste, Hektor este pus pe invatat, ci nu numai pe afaceri murdare, el ar vrea sa stie care e shukarimea maxima totala pe care ar putea sa o obtina daca el ar putea lua niste comentarii de pe drumul de la nodul $x ~i~$ la nodul $y ~i~$ cu proprietatea ca efortul lor de invatare total este cel mult egal cu $Emax ~i~$ (el isi devota putin timp pentru a invata, dar totusi are si niste afaceri mult mai importante de rezolvat si nu isi permite sa se oboseasca prea tare cu invatatul).

h2. Date de intrare

Fişierul de intrare $simulare.in$ contine pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se afla cate doua numere naturale $p$ si $g$. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre nodurile $x$ si $y$. Pe urmatoarele $M$ linii se afla cate trei numere naturale $x$, $y$ si $G$.

Fişierul de intrare $simulare.in$ contine pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se afla cate doua numere naturale $s ~i~$ si $e ~i~$ ce reprezinta shukarimea si efortul de invatare al comentariului din nodul $i$. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre nodurile $x$ si $y$. Pe urmatoarele $M$ linii se afla cate trei numere naturale $x ~i~$, $y ~i~$ si $Emax ~i~$.

h2. Date de ieşire

În fişierul de ieşire $simulare.out$ contine $M$ linii, pe linia $i$ fiind raspusnul la query-ul $i$.

În fişierul de ieşire $simulare.out$ contine $M$ linii, pe linia $i$ fiind suma shukarimii maxima posibila a unei submultimi de comenatrii de pe drumul de la nodul $x ~i~$ la nodul $y ~i~$ cu propietatea ca suma eforturilor acestora este mai mica sau egala cu $Emax ~i~$.

h2. Restricţii
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$

* $1 ≤ G ≤ 1000$
* $1 ≤ p ≤ 1.000.000$

* $1 ≤ Emax ~i~ ≤ 1000$
* $1 ≤ s ~i~ ≤ 1.000.000$

h2. Exemplu