题目描述

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 国的凛，为了决定住在哪个岛屿，决定按如下方式计算每个岛屿的“不便度”。岛屿 $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$ 的不便度。给定建设计划和候选迁居岛屿的信息，请编写程序求出这些岛屿的不便度。

输入格式

输入从标准输入中以以下格式给出：

$N\ M\ Q$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_M\ B_M\ C_M$
$X_1$
$X_2$
$\vdots$
$X_Q$

输出格式

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

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

7
3

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

12
8
7
10
13

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

43

提示

样例解释 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 \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 2000,\ M \le 2000$
2. (8 分) $N \le 2000$
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 分) 无额外限制

翻译由 DeepSeek 完成