Fişierul intrare/ieşire:	simulare.in, simulare.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 17
Autor	Chichirim George	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.3 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Simulare

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 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).

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 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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ N ≤ 2000
• 1 ≤ M ≤ 20000
• 1 ≤ Emax _i ≤ 1000
• 1 ≤ s _i ≤ 1.000.000

Exemplu

Explicaţie

...

Cum se trimit solutii?