P9531 [JOIST 2022] Reconstruction Project / Reconstruction Project

JOISC2022 D4T3.

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$.

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 $Q$ lines. The $j$-th line $(1\le j\le Q)$ contains one integer, the minimum cost required to satisfy company $j$.

**[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