== 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. 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 va trebui sa fie inchiriata masina electrica de o anumita capacitate)

h2. Date de intrare