Problem Background

JOISC2022 D4T3

Problem Description

JOI Town was once a thriving industrial area with numerous railways and train stations built for transporting products. Despite its decline, many unused railways and train stations still exist.

There are $N$ train stations in JOI Town, numbered $1, 2, \dots, N$. There are also $M$ remaining railways. The $i$-th railway ($1 \le i \le M$) connects train stations $A_i$ and $B_i$ bidirectionally with a width of $W_i$. It is guaranteed that any train station can be reached from any other train station via some railways.

You are the mayor of JOI Town. You plan to attract railway companies to use the remaining railways and train stations in JOI Town to revive it as the "Railway Town."

Thus, $Q$ railway companies have applied to participate in this revival plan. However, different companies require railways of different widths. This means you need to rebuild these railways to match the requirements of the respective companies.

The railway width required by the $j$-th company ($1 \le j \le Q$) is $X_j$. To accommodate company $j$, the following condition must be met:
- Condition: Ensure that any train station can be reached from any other train station using only railways of width $X_j$.

To meet this condition, you can rebuild railways as follows:
- Rebuild: Select a railway and rebuild it to increase or decrease its width by $1$ at a cost of $1$. However, if its width is $1$, it cannot be decreased further.

To determine which companies you can accommodate, you need to calculate the minimum cost required to meet the requirements of company $j$.

Write a program that, given the information about the train stations, railways, and railway companies, computes the minimum cost required to accommodate company $j$.

Input Format

The first line contains two positive integers $N$ and $M$, representing the number of train stations and the number of railways, respectively.

The next $M$ lines contain three positive integers each, $A_i$, $B_i$, and $W_i$, representing the train stations connected by the $i$-th railway and its width.

The $(M+2)$-th line contains a positive integer $Q$, representing the number of railway companies.

The next $Q$ lines contain one positive integer each, $X_j$, representing the required railway width for the $j$-th railway company.

Output Format

Output $Q$ lines, where the $j$-th line ($1 \le j \le Q$) contains an integer representing the minimum cost required to accommodate company $j$.

Sample Input and Output

Input Sample #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

Output Sample #1

8
2
5
10
9
21

Input Sample #2

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

Output Sample #2

1
1
2
0

Input Sample #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

Output Sample #3

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

Notes/Hints

[Sample Explanation #1]

For example, to accommodate company $1$, if you rebuild the railways as follows, it will cost $8$:

1. Decrease the width of railway $6$ by $4$.
2. Decrease the width of railway $9$ by $3$.
3. Increase the width of railway $10$ by $1$.

It can be proven that it is impossible to accommodate company $1$ with a cost less than $8$. Therefore, output $8$ on the first line.

This sample satisfies the constraints of subtasks $1, 2, 4, 5, 6$.

[Sample Explanation #2]

This sample satisfies the constraints of all subtasks.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $2, 4, 5, 6$.

[Data Range]

For all data, the following constraints are satisfied:

• $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 < j \le M$).
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$).
• It is guaranteed that any train station can be reached from any other train station via some railways.
• $1 \le X_j \le 10^9$ ($1 \le j \le Q$).
• $X_j < X_{j+1}$ ($1 \le j < Q$).

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分