問題文

N 頂点の木があり、頂点には 1 から N までの番号が、辺には 1 から N-1 までの番号がついています。 辺 i は頂点 A_i と B_i を結ぶ辺です。

1 から M までの番号のついた M 人の人が、今からこの木の上を移動します。 人 i は、頂点 V_i から出発し、以下の操作をちょうど L_i 回行います。

• 今いる頂点に繋がっている辺を自由に一つ選び、その辺を通って隣の頂点へ移動する。 このとき、通った辺の番号が x なら、C_x 点を得る。

すべての i について、人 i が L_i 回の操作で得られる得点の総和の最大値を求めてください。

制約

• 2 \leq N \leq 10^5
• 1 \leq A_i < B_i \leq N
• 1 \leq C_i \leq 10^9
• 1 \leq M \leq 10^5
• 1 \leq V_i \leq N
• 1 \leq L_i \leq 10^9
• 入力で与えられるグラフは木である。
• 入力される値はすべて整数である。

入力例 1

5
1 2 5
2 3 2
3 4 4
3 5 2
3
5 3
2 1
5 5

出力例 1

10
5
19

人 1 は、次のように行動すると 3 回の操作で得られる得点の総和を最大化できます。

• 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
• 辺 3 を使って移動し、頂点 3 から頂点 4 に移動する。4 点を得る。
• 辺 3 を使って移動し、頂点 4 から頂点 3 に移動する。4 点を得る。

人 2 は、次のように行動すると 1 回の操作で得られる得点の総和を最大化できます。

• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

人 3 は、次のように行動すると 5 回の操作で得られる得点の総和を最大化できます。

• 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
• 辺 2 を使って移動し、頂点 3 から頂点 2 に移動する。2 点を得る。
• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
• 辺 1 を使って移動し、頂点 1 から頂点 2 に移動する。5 点を得る。
• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

入力例 2

12
9 10 13
5 8 78
1 7 96
3 5 56
7 9 99
4 12 36
7 12 45
7 11 37
8 9 69
2 7 60
6 7 71
10
9 7
8 1
1 2
11 18
1 18
3 5
9 17
9 13
9 16
5 5

出力例 2

693
78
195
1720
1779
401
1683
1287
1584
444