AT_joisc2022_l 復興事業 (Reconstruction Project)
题目描述
# [JOISC2022] 复兴计划
## 题目背景
JOISC2022 D4T3
JOI 镇是一个曾经辉煌的工业区。为了运输产品，其中建起了许多铁轨与火车站。尽管 JOI 镇已经衰落，那里仍有许多不再被使用的铁轨与火车站。
JOI 镇中有 $N$ 个火车站，编号为 $1,2,\dots,N$。其中还剩下 $M$ 条铁轨。第 $i$ 条铁轨 $(1\le i \le M)$ 双向连接火车站 $A_i$ 和 $B_i$，且其宽度为 $W_i$。保证能够从任意火车站经过若干条铁轨到达任意其他火车站。
你是 JOI 镇的镇长。你计划吸引铁路公司来使用 JOI 镇中留下的铁轨与火车站，使得 JOI 镇复苏成为「铁路之镇」。
于是，共有 $Q$ 个铁路公司申请参与这个复兴计划。然而，不同公司的火车所需的铁轨宽度也有所不同。这意味着你需要重建这些铁轨，使得它们都匹配对应公司的火车。
第 $j$ $(1\le j\le Q)$ 家铁路公司的火车所需的铁轨宽度为 $X_j$。为了迎合公司 $j$，要求满足以下条件：
- **条件**：保证能够从任意火车站只经过宽度为 $X_j$ 的铁轨到达任意其他火车站。
为了满足上述条件，你可以按如下方式重建铁轨任意次：
- **重建**：选择一条铁轨，你可以重建其使得其宽度增加或减少 $1$ 并花费 $1$。然而，若其宽度为 $1$，则不能再减少其宽度。
为了确定你能满足哪些公司，你需要求出迎合公司 $j$ 所需要的最小花费。
请写一个程序，对于给定的火车站、铁轨与铁路公司的信息，计算迎合公司 $j$ 所需要的最小花费。
输入格式
第一行，两个正整数 $N,M$，表示火车站的个数和铁轨的条数。
接下来 $M$ 行，其中第 $i$ $(1 \le i \le M)$ 行包含三个正整数 $A_i, B_i, W_i$，表示第 $i$ 条铁轨连接的火车站和其宽度。
第 $M+2$ 行，一个正整数 $Q$，表示铁路公司的个数。
接下来 $Q$ 行，其中第 $j$ $(1 \le j \le Q)$ 行包含一个正整数 $X_j$，表示第 $j$ 个铁路公司的火车需要的铁路宽度。
输出格式
输出 $Q$ 行，第 $j$ $(1\le j\le Q)$ 包含一个整数，表示迎合公司 $j$ 所需要的最小花费。
## 样例 #1
### 样例输入 #1
```
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17
```
### 样例输出 #1
```
8
2
5
10
9
21
```
## 样例 #2
### 样例输入 #2
```
3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4
```
### 样例输出 #2
```
1
1
2
0
```
## 样例 #3
### 样例输入 #3
```
10 20
6 7 914727791
1 8 771674531
3 5 632918108
5 9 329296846
1 7 237501112
4 9 303328173
2 6 216298255
2 10 504024991
3 8 158236886
1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946
```
### 样例输出 #3
```
1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711
```
说明/提示
**【样例解释 #1】**
例如，为了迎合公司 $1$，若你按如下方式重建铁轨，将会花费 $8$。
1. 将铁轨 $6$ 的宽度减少 $4$。
2. 将铁轨 $9$ 的宽度减少 $3$。
3. 将铁轨 $10$ 的宽度增加 $1$。
可以证明不可能用少于 $8$ 的花费迎合公司 $1$。因此，在第一行输出 $8$。
该样例满足子任务 $1,2,4,5,6$ 的限制。
**【样例解释 #2】**
该样例满足所有子任务的限制。
**【样例解释 #3】**
该样例满足子任务 $2,4,5,6$ 的限制。
对于所有数据，满足：
- $2 \le N \le 500$。
- $N-1 \le M \le 100\,000$。
- $1 \le Q \le 1\,000\,000$。
- $1 \le A_i < B_i \le N$ $(1\le i\le M)$。
- $1 \le W_i \le 10^9$ $(1\le i\le M)$。
- $(A_i,B_i,W_i)\ne(A_j,B_j,W_j)$ $(1\le i