Background

JOISC2022 D4T3.

Problem Description

JOI Town was once a prosperous industrial area. To transport products, many rail tracks and train stations were built there. Although JOI Town has declined, there are still many unused rail tracks and train stations.

There are $N$ train stations in JOI Town, numbered $1,2,\dots,N$. There are $M$ remaining rail tracks. The $i$-th track $(1\le i \le M)$ connects stations $A_i$ and $B_i$ in both directions, and its width is $W_i$. It is guaranteed that you can travel from any station to any other station by passing through some tracks.

You are the mayor of JOI Town. You plan to attract railway companies to use the remaining tracks and stations, so that JOI Town will revive and become a “railway town”.

So, there are $Q$ railway companies applying to join this reconstruction project. However, different companies’ trains require different track widths. This means you need to rebuild these tracks so that they match the trains of each company.

The track width required by company $j$ $(1\le j\le Q)$ is $X_j$. To satisfy company $j$, the following condition must hold:

• Condition: It is possible to travel from any station to any other station using only tracks of width $X_j$.

To satisfy the condition above, you may rebuild tracks any number of times in the following way:

• Rebuild: Choose a track. You may rebuild it to increase or decrease its width by $1$ at a cost of $1$. However, if its width is $1$, you cannot decrease it further.

To determine which companies you can satisfy, you need to find the minimum cost required to satisfy company $j$.

Write a program that, given the information about stations, tracks, and companies, computes the minimum cost required to satisfy company $j$.

Input Format

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

The next $M$ lines describe the tracks. The $i$-th line $(1 \le i \le M)$ contains three positive integers $A_i, B_i, W_i$, meaning that the $i$-th track connects these two stations and has width $W_i$.

Line $M+2$ contains one positive integer $Q$, representing the number of railway companies.

The next $Q$ lines describe the companies. The $j$-th line $(1 \le j \le Q)$ contains one positive integer $X_j$, representing the required track width for the $j$-th company’s trains.

Output Format

Output $Q$ lines. The $j$-th line $(1\le j\le Q)$ contains one integer, the minimum cost required to satisfy company $j$.

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

8
2
5
10
9
21

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

1
1
2
0

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

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

Hint

[Sample Explanation #1]

For example, to satisfy company $1$, if you rebuild the tracks as follows, the total cost will be $8$.

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

It can be proven that it is impossible to satisfy 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$.

[Constraints]

For all testdata:

• $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)$.
• It is guaranteed that you can travel from any station to any other station by passing through some tracks.
• $1 \le X_j \le 10^9$ $(1\le j\le Q)$.
• $X_j < X_{j+1}$ $(1\le j<Q)$.

The additional constraints and scores for subtasks are given in the table below:

Translated by ChatGPT 5