The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction ProjectReconstruction Project
JOI Town is an industrial area which had flourished some time ago. In order to transport products, manystations and railway tracks were constructed. Though it declined, there remain the stations and the railway
tracks which are not used any more.
There are N stations in JOI Town, numbered from 1 to N. There remain M railway tracks. The i-th railway
track (1 ≤ i ≤ M) connects the station Ai and the station Bi bidirectionally. The width of the i-th railway track
is Wi . It is possible to travel from any station to any other station using railway tracks.
You are the mayor of JOI Town. You are planning to attract a railroad company using the remaining stations
and railway tracks, and revive the JOI Town as the town of railway. Then, Q railroad companies applied for thisrevival project. However, the width of the railway track for trains varies for diﬀerent companies. It turns outthat they need to reconstruct the railway tracks so that the width of the railway tracks of JOI Town matches thewidth of the railway tracks for the trains of a company.
The width of the railway tracks for the trains of the railroad company j (1 ≤ j ≤ Q) is X j . To attract therailroad company j, it is required that the following condition is satisfied.
Condition It is possible to travel from any station to any other station using railway tracks of width X j only.
In order to satisfy the above condition, you can reconstruct the railway tracks as many times as needed.
Reconstruction You choose a railway track. Then you reconstruct the chosen track so that its width will beincreased or decreased by 1. The cost is 1. However, if the width of a railway track is 1, it
is impossible to decrease the width further.
In order to decide on the company to be attracted, you want to estimate the minimum cost to attract eachrailroad company.
White a program which, given information on the stations, the railway tracks, and the railroad companies,
calculates the minimum cost to attract each railroad company.

Reconstruction Project– 1 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project

Input
Read the following data from the standard input. Given values are all integers.
NMA1 B1 W1A2 B2 W2..
.
A M BM W M
QX1X2..
.
XQ

OutputWrite Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) of output should contain the minimum cost toattract the railroad company j.

Constraints• 2 ≤ N ≤ 500.
• N − 1 ≤ M ≤ 100 000.
• 1 ≤ Q ≤ 1 000 000.
• 1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M).
• 1 ≤ Wi ≤ 1 000 000 000 (= 109 ) (1 ≤ i ≤ M).
• (Ai , Bi , Wi ) , (A j , B j , W j ) (1 ≤ i < j ≤ M).
• It is possible to travel from any station to any other station using railway tracks.
• 1 ≤ X j ≤ 1 000 000 000 (= 109 ) (1 ≤ j ≤ Q).
• X j < X j+1 (1 ≤ j ≤ Q − 1).

Reconstruction Project– 2 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying TrialMarch 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction ProjectSubtasks
1. (3 points) M ≤ 16,Q ≤ 10.

2. (4 points) Q ≤ 10.
3. (7 points) Bi = Ai + 1 (1 ≤ i ≤ M).
4. (28 points) M ≤ 1 000.
5. (35 points) Q ≤ 20 000.
6. (23 points) No additional constraints.

Sample Input and Output
Sample Input 1Sample Output 15 1081 2 82

1 3 135

1 4 5101 5 119

1 5 3212 3 72 4 15
3 4 63 5 64 5 26368101317
For example, to attract the railroad company 1, it will cost 8 if you reconstruct the railway tracks as follows.
1. Decrease the width of the 6-th railway track by 4. The cost is 4.

Reconstruction Project– 3 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project

2. Decrease the width of the 9-th railway track by 3. The cost is 3.
3. Increase the width of the 10-th railway track by 1. The cost is 1.
It is impossible to attract the railroad company 1 at cost less than 8. Therefore, output 8 in the first line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.
Sample Input 2Sample Output 23 4

11 2 1

11 2 422 3 2

02 3 44123
4This sample input satisfies the constraints of all the subtasks.

Reconstruction Project– 4 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying TrialMarch 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction ProjectSample Input 3

Sample Output 3

10 201121073688

6 7 914727791

761832468

1 8 771674531

1026806785

3 5 632918108

1316097872

5 9 329296846

1321500065

1 7 237501112

1445238392

4 9 303328173

1637513141

2 6 216298255

1621778548

2 10 504024991

1733953031

3 8 158236886

1738749711

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
10115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946
This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.

Reconstruction Project– 5 / 5