V Absurdistane to s internetom nie je med lízať. Bežný internet je tam v takej kvalite, že kým načítaš stránku so správami, sú už neaktuálne. Aby to vláda zlepšila, rozhodla sa podporiť výstavbu optických liniek. Keďže s peniazmi hospodári zodpovedne, dotačný úrad má jedno posvätné pravidlo: podporiť sa smie iba linka medzi dvoma miestami, ktoré ešte spojené nie sú. Vďaka tomu medzi každými dvoma miestami v krajine vedie po optike práve jedna možná trasa – ani o linku viac, aby náhodou nevznikla nejaká podozrivo užitočná rezerva.

Ty zhodou okolností pracuješ v internetovej firme, ktorá musí pravidelne prenášať obrovské kvantá dát medzi svojimi dátovými centrami po celej krajine. Bežná sieť je pomalá, a preto chceš používať iba optiku. Lenže vzhľadom na veľký dopyt a preťaženú sieť nie je ľahké dostať sa k používaniu týchto liniek. Každú optickú linku prevádzkuje iný súkromný operátor a ponúka dve možnosti:

• Prenájom. Zaplatíš $R$ peňazí a linku môžeš neobmedzene používať počas jednej jednotky času.
• Odkúpenie. Zaplatíš $B$ peňazí a linku môžeš používať, kedykoľvek potrebuješ.

V diári máš rozpísané, kedy medzi ktorými dátovými centrami musia tiecť dáta. Každá požiadavka znie rovnako: „od času $l$ po čas $r$ (vrátane) musí byť možné preniesť dáta z miesta $a$ do miesta $b$.“ To znamená, že po všetkých linkách na trase z $a$ do $b$ musíš v každom okamihu z tohto intervalu smieť preniesť dáta, teda tie linky musíš mať vtedy buď prenajaté, alebo odkúpené.

Požiadavky ignorovať nemôžeš, pretože zákazníci sa na teba spoliehajú a peniazmi plytvať nechceš, lebo potom nezostane na odmeny pre teba (a tvojich kolegov). Zisti, koľko najmenej peňazí musíš dokopy zaplatiť za prenájom/odkúpenie kapacity na optických linkách.

Úloha

Máme strom s $n$ vrcholmi (miesta) a $n-1$ hranami (optické linky). Pri $i$-tej linke vieme buď zaplatiť $B_i$ a používať ju po celý čas, alebo za každú jednotku času, počas ktorej ju chceme používať, zaplatiť $R_i$.

Ďalej máme $m$ požiadaviek. $i$-ta požiadavka hovorí, že v každom okamihu času od $l_i$ po $r_i$ vrátane musia byť použiteľné všetky linky na (jedinej) trase medzi vrcholmi $a_i$ a $b_i$.

Nájdi najmenšiu možnú celkovú cenu, ktorou sa dajú splniť všetky požiadavky.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla $n$ a $m$ ($2 \leq n$, $1 \leq m$) – počet miest a počet požiadaviek.

Nasleduje $n-1$ riadkov popisujúcich linky. V $i$-tom z nich sú štyri celé čísla $u_i$, $v_i$, $B_i$, $R_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq B_i, R_i \leq 10^9$) – linka spája miesta $u_i$ a $v_i$, jej odkúpenie stojí $B_i$ peňazí a prenájom na jednu jednotku času stojí $R_i$ peňazí. Linky tvoria strom, teda medzi ľubovoľnými dvoma miestami vedie práve jedna trasa.

Nasleduje $m$ riadkov popisujúcich požiadavky. V $i$-tom z nich sú štyri celé čísla $a_i$, $b_i$, $l_i$, $r_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$, $1 \leq l_i \leq r_i$).

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo – najmenší počet peňazí, ktorý musíš dokopy zaplatiť.

Upozornenie: Výsledok sa nemusí zmestiť do 32-bitovej premennej.

Príklady

3 1
1 2 7 2
2 3 9 4
1 2 3 5

6

Požiadavka potrebuje iba linku medzi miestami $1$ a $2$, a to počas troch jednotiek času. Prenájom vyjde na $3 \cdot 2 = 6$ peňazí, čo je menej ako odkúpenie za $7$. Linku medzi $2$ a $3$ nepotrebujeme, takže za ňu nezaplatíme nič.

4 3
1 2 12 2
2 3 6 3
2 4 100 1
1 3 1 5
3 4 4 6
1 4 2 3

21

Linku $1-2$ potrebujeme v časoch $1$ až $5$ (prvá požiadavka) a $2$ až $3$ (tretia požiadavka), dokopy teda päť jednotiek času, čo nás pri prenájme vyjde na $5 \cdot 2 = 10$ peňazí. Linku $2-3$ potrebujeme šesť jednotiek času, prenájom by stál $18$, takže ju radšej odkúpime za $6$. Linku $2-4$ potrebujeme v časoch $2$ až $6$, čiže tiež päť jednotiek času, a prenajmeme ju za $5$ peňazí. Dokopy $10 + 6 + 5 = 21$.

Všimni si, že tretia požiadavka nás v skutočnosti nestála nič navyše – obe linky na jej trase sme aj tak už museli mať.