在 JOI 共和国中，有 $N$ 座城市，编号为 $1$ 到 $N$。这些城市由 $N-1$ 条道路连接。JOI 共和国的居民通过这些道路在城市间往来。他们可以通过每一条道路双向通行。任意两座城市之间都可以通过一条或多条道路到达。

IOI 先生是 JOI 共和国总统职位的候选人。当然，为了成为总统，他必须进行竞选活动。他的秘书制定了 $M$ 个竞选计划。在第 $i$ 个计划中，IOI 先生将从城市 $A_i$ 出发，沿最短路径前往城市 $B_i$，并在路径上的每一座城市（包括城市 $A_i$ 和城市 $B_i$）进行公开演讲。由于他的秘书非常出色，已知如果执行第 $i$ 个计划，IOI 先生将获得 $C_i$ 张选票。可以执行多个计划。

然而，JOI 共和国的居民缺乏耐心。如果 IOI 先生在同一座城市进行多次公开演讲，他将失去 JOI 共和国人民的支持。

因为 IOI 先生想成为总统，他希望获得尽可能多的选票。由于你是 JOI 共和国的超级程序员，他请求你编写一个程序，在假设他不会在同一座城市进行多次公开演讲的前提下，计算出 IOI 先生在总统选举中能获得的最大选票数。

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$，表示 JOI 共和国的城市数量。
• 接下来的 $N-1$ 行中的第 $i$ 行（$1 \le i \le N-1$）包含两个空格分隔的整数 $X_i, Y_i$。这意味着第 $i$ 条道路连接城市 $X_i$ 和城市 $Y_i$。
• 接下来的这一行包含一个整数 $M$，表示竞选计划的数量。
• 接下来的 $M$ 行中的第 $i$ 行（$1 \le i \le M$）包含三个空格分隔的整数 $A_i, B_i, C_i$。这意味着在第 $i$ 个计划中，IOI 先生将从城市 $A_i$ 出发，沿最短路径前往城市 $B_i$，如果执行该计划，他将获得 $C_i$ 张选票。

输出格式

输出一行，包含一个整数，表示 IOI 先生在总统选举中能获得的最大选票数。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 100\,000$
• $1 \le X_i \le N$
• $1 \le Y_i \le N$
• $X_i \neq Y_i$ ($1 \le i \le N-1$)
• 任意两座城市之间都可以通过一条或多条道路到达。
• $1 \le M \le 100\,000$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• $A_i \neq B_i$ ($1 \le i \le M$)
• $1 \le C_i \le 10\,000$

子任务

子任务 1 [10 分] * $M \le 15$

子任务 2 [5 分] $X_i = i$ ($1 \le i \le N-1$) $Y_i = i+1$ ($1 \le i \le N-1$) * $C_i = 1$ ($1 \le i \le M$)

子任务 3 [5 分] $X_i = i$ ($1 \le i \le N-1$) $Y_i = i+1$ ($1 \le i \le N-1$)

子任务 4 [30 分] * $C_i = 1$ ($1 \le i \le M$)

子任务 5 [10 分] $N \le 1\,000$ $M \le 1\,000$

子任务 6 [40 分] * 无附加限制。

样例

样例输入 1

7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

样例输出 1

19

说明 1

在此样例输入中，竞选的最优策略是执行计划 1 和计划 3。

样例输入 2

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

样例输出 2

18

说明 2

此样例输入满足子任务 3 的限制。

样例输入 3

10
10 6
2 7
1 9
9 8
3 8
6 4
7 8
5 4
4 8
7
1 3 1
4 10 1
2 8 1
5 3 1
3 7 1
8 5 1
1 9 1

样例输出 3

3

说明 3

此样例输入满足子任务 4 的限制。

样例输入 4

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204

样例输出 4

29191