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

Marele afacerist si artist, Sorin Pastrama, dorste sa isi petreaca vacanta de primavara in Cuba. Tara arata ca un arbore cu $N$ noduri, fiecare muchie avand o lungime. In fiecare nod se afla benzinarii si, de asemenea, pe fiecare muchie exista o masina electrica care poate cara o cisterna cu combustibil cu scopul de a-l ajuta pe domnul Pastrama sa traverseze muchia cu bine. Costul de a inchiria o astfel de masina electrica care sa care $x$ unitati de combustibil este de $x^2^$. Cu scopul de a-si planui calatoria, Pastrama va cere ajutorul si va roaga sa raspundeti la $Q$ query-uri de forma:

Marele afacerist si artist, Sorin Pastrama, dorste sa isi petreaca vacanta de primavara in Cuba. Tara arata ca un arbore cu $N$ noduri, fiecare muchie avand o lungime (acestea sunt bidirectionale). In fiecare nod se afla benzinarii (de la care iti poti face plinul) si, de asemenea, pe fiecare muchie exista o masina electrica care poate cara o cisterna cu combustibil cu scopul de a-l ajuta pe domnul Pastrama sa traverseze muchia cu bine. Costul de a inchiria o astfel de masina electrica care sa care $x$ unitati de combustibil este de $x^2^$. Cu scopul de a-si planui calatoria, Pastrama va cere ajutorul si va roaga sa raspundeti la $Q$ query-uri de forma:

* $X Y C$ -> care este costul minim pe care Pastrama trebuie sa-l plateasca firmei care inchiriaza acele masini electrice daca el doreste sa plece din nodul $X$ si sa ajunga in nodul $Y$, avand la dispozitie un Mercedes cu rezervorul de capacitate $C$ unitati de combustibil.

* $X Y C$ -> care este costul minim pe care Pastrama trebuie sa-l plateasca firmei care inchiriaza acele masini electrice daca el doreste sa plece din nodul $X$ si sa ajunga in nodul $Y$, avand la dispozitie un Mercedes cu rezervorul de capacitate $C$ unitati de combustibil? (anumite muchii vor avea lungimea mai mare ca $C$, asadar pe aceste muchii masina electrica de o anumita capacitate va fi inchiriata)

h2. Date de intrare

Fişierul de intrare $cuba.in$ contine pe prima linie numerele naturale $N$ si $Q$, cu semnificatiile din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale T ~i~ si L ~i~ care reprezinta tatal nodului $i$ si lungimea muchiei respective ( $2 ≤ i ≤ N$ ). Radacina arborelui este nodul $1$. Pe urmatoarele $Q$ linii se afla cate 3 numere $X$ $Y$ $C$, cu semnficatiile din enunt.

Fişierul de intrare $cuba.in$ contine pe prima linie numerele naturale $N$ si $Q$, cu semnificatiile din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $T$~$i$~ si $L$~$i$~ care reprezinta tatal nodului $i$ si lungimea muchiei respective $(2 ≤ i ≤ N)$. Radacina arborelui este nodul $1$. Pe urmatoarele $Q$ linii se afla cate 3 numere $X$ $Y$ $C$, cu semnficatiile din enunt.

h2. Date de ieşire

În fişierul de ieşire $cuba.out$ contine $Q$ linii, pe fiecare linie aflandu-se raspunsul la cate un query, in ordinea in care acestea apar in fisierul de intrare.

Fişierul de ieşire $cuba.out$ contine $Q$ linii, pe fiecare linie aflandu-se raspunsul la cate un query, in ordinea in care acestea apar in fisierul de intrare.

h2. Restricţii
* $1 ≤ N, Q ≤ 10^5^$

* $1 ≤ L ~i~, C ≤ 10^5^$

* $1 ≤ $L$~$i$~, C ≤ 10^5^$

* $1 ≤ X, Y ≤ N$

* Pentru a parcurge o distanta de lungime $x$, sunt necesare $x$ unitati de combustibil.

* **Pentru a parcurge o distanta de lungime $x$, sunt necesare $x$ unitati de combustibil.**
* Oricat de mult si-ar dori Pastrama sa isi petreaca cat mai mult timp cu soferita cubaneza a masinii electrice, acesta vrea sa isi pastreze banii ca sa mearga si prin alte tari straine.

h2. Exemplu

h3. Explicaţie

...

Primul query: Rezervorul de capacitate $4$ este de ajuns pentru muchiile $5 -> 2$ si $2 -> 1$, dar nu este de ajuns pentru muchia $1 -> 5$. Pentru aceasta muchie este nevoie de inca o unitate de combustibil in plus. Deci, costul este $1^2^ = 1$.
Al doilea query: Pentru muchiile $2 -> 1$ si $1 -> 5$ sunt necesare inca $2$, respectiv $3$ unitati de combustibil. Deci, costul este $2^2^ + 3^2^ = 13$.
Al treilea query: Rezervorul de capacitate $3$ este de ajuns pentru fiecare muchie de pe drumul de la nodul $4$ la nodul $5$. Deci, costul este $0$.

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