Problem C
Den generösa resenären

Din rika kompis Erika bor i ett land med $N$ byar där den $i$:te byn har $A_ i$ invånare. Byarna är kopplade med varandra med $N-1$ vägar så att det går att ta sig från en godtycklig by till en annan godtycklig by genom vägarna.

Efter en hel dags arbete är Erika utmattad och behöver därför gå på semester, så hon planerar att besöka några av landets byar. Som alla rika människor så finns det inget din kompis gillar mer än att ge bort pengar! Hon planerar därför att ta med sig en stor påse med enkronor och ge bort så mycket pengar som hon kan i varje by hon besöker (inklusive den hon startar i).

Det finns dock ett problem: om en invånare i en by får mindre pengar än en annan invånare i samma by så blir hen jättearg och Erikas liv blir hotat. För att undvika detta bestämmer hon sig för att ge alla invånare så mycket pengar hon kan så att alla i samma by får lika mycket pengar, även om det betyder att ingen får pengar.

Nu undrar Erika hur mycket pengar hon kommer ha vid slutet av en sådan resa. Hon ställer $Q$ frågor till dig av formen: Givet att resan startar vid by $u$ med $x$ 1-kronor, och slutar vid by $v$, hur mycket pengar kommer finnas kvar vid slutet av resan?

Notera att resan alltid följer den enkla vägen mellan två byar, d.v.s. den enda kortaste vägen. Erika delar endast ut hela enkronor, så hon ger alltid ett icke-negativt heltal pengar till varje bybo.

Indata

Den första raden innehåller de två heltalen $N$ ($1\leq N \leq 2 \cdot 10^5$) och $Q$ ($1 \leq Q \leq 10^5$).

Därefter följer $N-1$ rader, den $i$:te raden innehåller två tal $a_ i$ $b_ i$, ($1 \leq a_ i,b_ i \leq N$). Detta betyder att det finns en väg mellan byarna $a_ i$ och $b_ i$.

Sedan följer en rad med $N$ heltal där det $i$:te talet, $1\leq A_ i \leq 10^9$, beskriver antalet invånare i by $i$.

Till slut följer $Q$ rader, en per fråga. Den $i$:te raden består av heltal $u_ i$, $v_ i$, $x_ i$ ($1 \leq u_ i,v_ i \leq N$, $1 \leq x_ i \leq 10^9$), där $u_ i$ är startbyn, $v_ i$ är slutbyn och $x_ i$ är antalet enkronor Erika börjar med i den $i$:te frågan.

Utdata

Skriv ut $Q$ rader: den $i$:te raden ska innehålla svaret av den $i$:te frågan.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

1 Exempelförklaring

I det första testfallet sker den första resan mellan by $8$ och by $10$, och Erika börjar med $31$ kronor. Redan i den första byn (med $20$ invånare) ger hon bort $1$ krona till varje person, och har $11$ kvar. Resan går därefter vidare till by $7$, med $10$ invånare. Även här ger Erika bort en krona till varje person, och har nu bara en krona kvar. Till sist når Erika by $10$, med $20$ invånare. Här har tyvärr inte Erika råd att ge bort några pengar till befolkningen, utan hon stannar på $1$ krona kvar.

Det andra testfallet är ett exempel på ett testfall som kan dyka upp i testfallsgrupp 1, 2 och 3.

10 7
1 2
2 5
5 3
2 6
6 7
7 8
7 10
1 4
1 9
5 8 10 10 9 5 10 20 3 20
8 10 31
3 9 5
3 9 14
8 3 34
1 6 8
7 2 19
10 4 43

1
0
1
4
3
4
3

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

4
0
1