JOI 小镇曾经是一个繁荣的工业区。为了运输产品，人们修建了许多车站和铁轨。尽管现在已经衰落，但仍保留着一些不再使用的车站和铁轨。

JOI 小镇有 $N$ 个车站，编号为 $1$ 到 $N$。目前保留了 $M$ 条铁轨。第 $i$ 条铁轨（$1 \le i \le M$）连接车站 $A_i$ 和车站 $B_i$，且是双向的。第 $i$ 条铁轨的宽度为 $W_i$。目前可以通过铁轨从任意车站到达其他任何车站。

你是 JOI 小镇的镇长。你计划利用现有的车站和铁轨吸引一家铁路公司，使 JOI 小镇重现铁路城镇的辉煌。随后，有 $Q$ 家铁路公司申请了这个复兴项目。然而，不同公司对列车铁轨的宽度要求各不相同。因此，他们需要改造铁轨，使得 JOI 小镇的铁轨宽度与该公司列车的铁轨宽度相匹配。

第 $j$ 家铁路公司（$1 \le j \le Q$）的列车铁轨宽度为 $X_j$。为了吸引第 $j$ 家铁路公司，必须满足以下条件：

条件：仅使用宽度为 $X_j$ 的铁轨，即可从任意车站到达其他任何车站。

为了满足上述条件，你可以根据需要多次改造铁轨。

改造：你选择一条铁轨，将其宽度增加或减少 $1$。成本为 $1$。但是，如果铁轨的宽度为 $1$，则无法进一步减小宽度。

为了决定吸引哪家公司，你需要估算吸引每家铁路公司的最低成本。

请编写一个程序，在给定车站、铁轨和铁路公司信息的情况下，计算吸引每家铁路公司的最低成本。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ M$ $A_1 \ B_1 \ W_1$ $A_2 \ B_2 \ W_2$ $\vdots$ $A_M \ B_M \ W_M$ $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含吸引第 $j$ 家铁路公司的最低成本。

数据范围

• $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 1\,000\,000\,000$ ($= 10^9$) ($1 \le i \le M$)
• $(A_i, B_i, W_i) \neq (A_j, B_j, W_j)$ ($1 \le i < j \le M$)
• 可以通过铁轨从任意车站到达其他任何车站。
• $1 \le X_j \le 1\,000\,000\,000$ ($= 10^9$) ($1 \le j \le Q$)
• $X_j < X_{j+1}$ ($1 \le j \le Q - 1$)

子任务

1. (3 分) $M \le 16$, $Q \le 10$
2. (4 分) $Q \le 10$
3. (7 分) $B_i = A_i + 1$ ($1 \le i \le M$)
4. (28 分) $M \le 1\,000$
5. (35 分) $Q \le 20\,000$
6. (23 分) 无附加限制

样例

样例输入 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

说明

例如，要吸引第 $1$ 家铁路公司（$X_1 = 3$），如果按以下方式改造铁轨，成本为 $8$： 1. 将第 $6$ 条铁轨的宽度减少 $4$。成本为 $4$。 2. 将第 $9$ 条铁轨的宽度减少 $3$。成本为 $3$。 3. 将第 $10$ 条铁轨的宽度增加 $1$。成本为 $1$。 总成本为 $4 + 3 + 1 = 8$。无法以低于 $8$ 的成本吸引第 $1$ 家铁路公司。

样例输入 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

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