問題文

ある地方では点が村に、街道が線で木構造をなしている地域がありました。
その土地の領主はとても貪欲で全ての村に関所を設けることとなりました。
行商人は村を通るたびに一人頭一定額の通行税を納めることになります。
貴方は領主に雇われた会計主任です。
与えられたデータから行商人全員が納める税額の総計を求めるように言われました。
貴方は何も気にせず税額の総計を一行に出力するプログラムを書いてください。
領主の貪欲な税がどんな未来を算出するのか、それは貴方が気にすることではありません。
（注、気楽に挑戦してもらうために採点データは税や行商人の人数は非常に小さい値に設定した。非常に特殊な集計をしても６４ビット整数値に収まるように設定している）
村のデータと行商人の木構造上での移動ルートが与えられるので税収の総額を計算せよ。

入力

$N$
$A_1\ B_1$
$\dots$
$A_i\ B_i$
$\dots$
$A_{N-1}\ B_{N-1}$
$U_1$
$\dots$
$U_i$
$\dots$
$U_N$
$M$
$A_1\ B_1\ C_1$
$\dots$
$A_i\ B_i\ C_i$
$\dots$
$A_M\ B_M\ C_M$

一行目に村の数$2\le N \le 100000$
続く$N-1$行に村と村をつなぐ街道を現すデータが与えられます。
意味は$A_i$と$B_i$の村が街道でつながっており双方向に移動可能。
村は$0～N-1$までの番号が割り振られていると仮定してよい。
続く$N$行に、領主の定めた各村の通行税の額が村$0$～村$N-1$まで順番に整数$U_i$で与えられる。 $0\lt U_i \le 100$の自然数
次に行商人のデータ数Mが一行に整数で$0\le M \le 200000$
続くM行にわたり
$A_i$は出発の村 $0 \le A_i \le N-1$
$B_i$は目的の村 $0 \le B_i \le N-1$
$C_i$はその移動をする行商人の人数です。$1 \le C_i \le 10$
行商人は全て出発の村$A_i$で通行税を納め途中経路の村村で税を納め目的の村$B_i$で税を納める必要があります。
それもどこでも$C_i$人分です。

出力

S

サンプル