JOI 国是一个由 $N$ 个岛屿组成的国家，岛屿编号为 $1$ 到 $N$。目前，该国岛屿之间没有任何桥梁相连，居民们生活很不方便。

因此，作为 JOI 国的大臣，你决定开展一项国家工程，新建一些桥梁。共有 $M$ 个建桥计划，第 $j$ 个建桥计划（$1 \le j \le M$）是以费用 $C_j$ 在岛屿 $A_j$ 和岛屿 $B_j$ 之间架设一座双向通行的桥梁。这里保证 $C_1, C_2, \dots, C_M$ 两两不同。此外，保证如果执行所有的建桥计划，所有岛屿都可以通过若干座桥梁互相到达。

由于 JOI 国的预算有限，你决定按以下方式实施国家工程：

1. 从 $N$ 个岛屿中选择一个岛屿 $s$ 作为首都。

2. 进行以下操作 $N - 1$ 次：

   • 在每次操作之前，将通过若干座桥梁可以从首都到达的岛屿称为“近岛”，否则称为“远岛”。在所有一端是近岛、另一端是远岛的建桥计划中，选择费用最低的一个并执行。

3. 进行 $N - 1$ 次操作后，结束国家工程。

根据建桥计划满足的约束条件，可以证明以下结论：

• 在每次操作中，一定存在可以选择的建桥计划。此外，每次执行的建桥计划是唯一确定的。
• 在该工程结束时，所有岛屿都可以通过若干座桥梁互相到达。

正在考虑移居到 JOI 国的凛（Rin）为了参考应该住在哪个岛屿，决定按如下方式计算每个岛屿的不便度。岛屿 $i$（$1 \le i \le N$）的不便度定义如下：

• 设以岛屿 $s$（$1 \le s \le N$）为首都实施国家工程时，岛屿 $i$ 变得可以从首都到达之前所执行的建桥计划数量为 $D_{s,i}$。这里，当 $s = i$ 时，$D_{s,i}$ 为 $0$。
• 岛屿 $i$ 的不便度定义为对于所有 $1 \le s \le N$ 的 $D_{s,i}$ 的总和。

凛想要计算她作为搬迁候选地的 $Q$ 个岛屿 $X_1, X_2, \dots, X_Q$ 的不便度。给定建桥计划和搬迁候选岛屿的信息，请编写一个程序来计算这些岛屿的不便度。

输入格式

输入按以下形式从标准输入给出：

$$ \begin{array}{l} N \quad M \quad Q \\ A_1 \quad B_1 \quad C_1 \\ A_2 \quad B_2 \quad C_2 \\ \vdots \\ A_M \quad B_M \quad C_M \\ X_1 \\ X_2 \\ \vdots \\ X_Q \end{array} $$

输出格式

输出 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）输出岛屿 $X_k$ 的不便度。

数据范围

• $2 \le N \le 300\,000$。
• $1 \le M \le 600\,000$。
• $1 \le Q \le N$。
• $1 \le A_j < B_j \le N$（$1 \le j \le M$）。
• 如果执行所有的建桥计划，所有岛屿都可以通过若干座桥梁互相到达。
• $1 \le C_j \le 10^9$（$1 \le j \le M$）。
• $C_1, C_2, \dots, C_M$ 两两不同。
• $1 \le X_k \le N$（$1 \le k \le Q$）。
• $X_1, X_2, \dots, X_Q$ 两两不同。
• 输入的所有值均为整数。

子任务

1. (5 分) $N \le 2\,000$，$M \le 2\,000$。
2. (8 分) $N \le 2\,000$。
3. (9 分) $M = N - 1$，$A_j = j, B_j = j + 1$（$1 \le j \le M$），$Q = 1$。
4. (18 分) $M = N - 1$，$A_j = j, B_j = j + 1$（$1 \le j \le M$）。
5. (28 分) $Q = 1$。
6. (32 分) 无追加限制。

样例

输入样例 1

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

输出样例 1

7
3

说明 1

例如，考虑以岛屿 $1$ 为首都实施国家工程的情况。此时，建桥计划将按以下顺序执行：

1. 执行第 $1$ 个建桥计划。从首都开始，岛屿 $3$ 变得可以到达。
2. 执行第 $3$ 个建桥计划。从首都开始，岛屿 $2$ 变得可以到达。
3. 执行第 $5$ 个建桥计划。从首都开始，岛屿 $4$ 变得可以到达。

由此，得到 $D_{1,1} = 0, D_{1,2} = 2, D_{1,3} = 1, D_{1,4} = 3$。

由于 $D_{2,1} = 2, D_{3,1} = 2, D_{4,1} = 3$，因此岛屿 $1$ 的不便度为 $D_{1,1} + D_{2,1} + D_{3,1} + D_{4,1} = 0 + 2 + 2 + 3 = 7$。

此外，由于 $D_{2,3} = 1, D_{3,3} = 0, D_{4,3} = 1$，因此岛屿 $3$ 的不便度为 $D_{1,3} + D_{2,3} + D_{3,3} + D_{4,3} = 1 + 1 + 0 + 1 = 3$。

该样例满足子任务 1, 2, 6 的限制。

输入样例 2

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

输出样例 2

12
8
7
10
13

说明 2

该样例满足子任务 1, 2, 4, 6 的限制。

输入样例 3

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

输出样例 3

43

说明 3

该样例满足子任务 1, 2, 5, 6 的限制。