시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB39181551.724%

문제

JOI Town is an industrial area which had flourished some time ago. In order to transport products, many stations 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 $A_i$ and the station $B_i$ bidirectionally. The width of the $i$-th railway track is $W_i$. 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 this revival project. However, the width of the railway track for trains varies for different companies. It turns out that they need to reconstruct the railway tracks so that the width of the railway tracks of JOI Town matches the width 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 Xj . To attract the railroad 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 be increased 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 each railroad 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.

입력

Read the following data from the standard input. Given values are all integers.

$\begin{align*}& 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  \end{align*}$

출력

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

제한

  • $2 ≤ N ≤ 500$.
  • $N - 1 ≤ M ≤ 100\,000$.
  • $1 ≤ Q ≤ 1\,000\,000$.
  • $1 ≤ A_i < B_i ≤ N$ ($1 ≤ i ≤ M$).
  • $1 ≤ W_i ≤ 1\,000\,000\,000$ ($= 10^9$) ($1 ≤ i ≤ M$).
  • $(A_i , B_i , W_i) \ne (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$ ($= 10^9$) ($1 ≤ j ≤ Q$).
  • $X_j < X_{j+1}$ ($1 ≤ j ≤ Q - 1$).

서브태스크

번호배점제한
13

$M ≤ 16$, $Q ≤ 10$.

24

$Q ≤ 10$.

37

$B_i = A_i + 1$ ($1 ≤ i ≤ M$).

428

$M ≤ 1\,000$.

535

$Q ≤ 20\,000$.

623

No additional constraints.

예제 입력 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

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

예제 입력 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

This sample input satisfies the constraints of all the subtasks.

예제 입력 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

This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.

채점 및 기타 정보

  • 예제는 채점하지 않는다.