== include(page="template/taskheader" task_id="simulare") ==
Poveste şi cerinţă...
Deoarece anul trecut nu ati reusit sa-l ajutati pe 'Hektor':http://www.infoarena.ro/problema/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 <tex>N</tex> 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 doua numere <tex>S</tex> si <tex>E</tex>, <tex>S</tex> reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar <tex>E</tex> reprezentand efortul necesar de a-l toci. Mai sunt fix <tex>M</tex> zile pana la simulare, iar Hektor isi stie programul struna. Pentru fiecare zi <tex>i</tex> din cele <tex>M</tex>, el are niste afaceri de indeplinit, astfel acesta fiind nevoit sa se deplaseze din nodul <tex>x_i</tex> in nodul <tex>y_i</tex>. Deoarece, anul acesta, 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 <tex>x_i</tex> la nodul <tex>y_i</tex> cu proprietatea ca efortul lor de invatare total este cel mult egal cu <tex>Emax_i</tex> (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 <tex>S_i</tex> si <tex>E_i</tex> 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 <tex>x_i</tex>, <tex>y_i</tex> si <tex>Emax_i</tex>.
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$ trebuie sa se afle $M$ linii, pe linia $i$ fiind suma shukarimii maxima posibila a unei submultimi de comenatrii de pe drumul de la nodul <tex>x_i</tex> la nodul <tex>y_i</tex> cu propietatea ca suma eforturilor acestora este mai mica sau egala cu <tex>Emax_i</tex>.
h2. Restricţii
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$
* $1 ≤ G ≤ 1000$
* $1 ≤ P ≤ 10^6$
* $1 ≤$ <tex>Emax_i</tex> $≤ 1000$
* $1 ≤$ <tex>s_i</tex> ≤ $1.000.000$
h2. Exemplu
