Railway Revival

JOI Town was once a brilliant industrial area with many railroads and train stations. Although the town has since declined, there still remain unused rails and stations.

The town has \(N\) train stations numbered \(1,2,\dots,N\) and \(M\) railroad tracks. The \(i\)-th track (\(1\le i\le M\)) connects station \(A_i\) and station \(B_i\) bidirectionally and has a width of \(W_i\). It is guaranteed that any station can reach any other station through some sequence of tracks.

As the mayor of JOI Town, you plan to revive the town by inviting railway companies to use these abandoned tracks and stations.

There are \(Q\) railway companies applying, and each company has a train that requires a specific rail width \(X_j\). In order to accommodate company \(j\), you must ensure that:

• Condition: It must be possible to travel between any two stations using only tracks whose current width is exactly \(X_j\).

To fulfill this condition, you can rebuild tracks arbitrarily many times. In each rebuild operation, you select one track and change its width by \(\pm1\) (it costs 1 per unit change). Note that if a track's width is \(1\), its width cannot be decreased.

Your task is to compute, for each company \(j\), the minimum total cost required to achieve the condition.

Hint: One possible strategy is to choose a subset of tracks forming a spanning tree. For each selected track, the cost is \(|W_i - X_j|\). You need to choose the spanning tree with the minimum total adjustment cost.

inputFormat

The input is given as follows:

N M
A1 B1 W1
A2 B2 W2
... 
AM BM WM
Q
X1
X2
... 
XQ

It is guaranteed that the original set of tracks connects all \(N\) stations.

outputFormat

For each query, print on a new line the minimum total cost required to adjust some tracks so that the train stations become connected when using only tracks of width exactly \(X_j\).

sample

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

1
1