说明

在 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 共和国的超级程序员，因此他请你编写一个程序，在假设他不会在同一座城市发表演讲超过一次的前提下，计算他在总统选举中能获得的最大选票数。

任务

给定 JOI 共和国的城市数量 $N$、道路信息、竞选计划的数量 $M$ 以及每个计划的信息，编写一个程序计算 IOI 先生在总统选举中能获得的最大选票数。

输入格式

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

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

输出格式

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

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

19

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

18

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

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

29191

提示

样例 1 解释

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

样例 2 解释

此样例输入满足子任务 3 的约束条件。

样例 3 解释

此样例输入满足子任务 4 的约束条件。

约束条件

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

• $2 \leq N \leq 100\,000$。
• $1 \leq X_i \leq N$。
• $1 \leq Y_i \leq N$。
• $X_i \ne Y_i$（$1 \leq i \leq N-1$）。
• 人们可以通过一条或多条道路在任意两座城市之间往来。
• $1 \leq M \leq 100\,000$。
• $1 \leq A_i \leq N$。
• $1 \leq B_i \leq N$。
• $A_i \ne B_i$（$1 \leq i \leq M$）。
• $1 \leq C_i \leq 10\,000$。

子任务

子任务 1 [10 分]

• $M \leq 15$。

子任务 2 [5 分]

• $X_i = i$（$1 \leq i \leq N-1$）。
• $Y_i = i+1$（$1 \leq i \leq N-1$）。
• $C_i = 1$（$1 \leq i \leq M$）。

子任务 3 [5 分]

• $X_i = i$（$1 \leq i \leq N-1$）。
• $Y_i = i+1$（$1 \leq i \leq N-1$）。

子任务 4 [30 分]

• $C_i = 1$（$1 \leq i \leq M$）。

子任务 5 [10 分]

• $N \leq 1\,000$。
• $M \leq 1\,000$。

子任务 6 [40 分]

• 无额外约束。

翻译由 DeepSeek V3.2 完成