재건 프로젝트

JOI 타운은 한때 번성했던 공업 지역이다. 제품을 운송하려고 많은 역과 철도 선로가 건설되었다. 지금은 쇠퇴했지만, 더 이상 쓰이지 않는 역과 철도 선로가 아직 남아 있다.

JOI 타운에는 $1$번부터 $N$번까지 번호가 붙은 역이 $N$개 있다. 남아 있는 철도 선로는 $M$개이며, $i$번째 철도 선로($1 \le i \le M$)는 역 $A_i$와 역 $B_i$를 양방향으로 잇고 너비는 $W_i$이다. 어느 역에서든 철도 선로를 따라 다른 모든 역으로 이동할 수 있다.

당신은 JOI 타운의 시장이다. 남은 역과 철도 선로를 활용해 철도 회사를 유치하고, 이 도시를 철도 도시로 되살리려 한다. 이를 위해 $Q$개의 철도 회사가 재건 사업에 지원했다. 회사마다 열차가 쓰는 선로 너비가 다르다. 회사 $j$($1 \le j \le Q$)의 열차 선로 너비는 $X_j$이다. 회사 $j$를 유치하려면 다음 조건을 만족해야 한다.

조건: 너비가 $X_j$인 철도 선로만 사용해서 어느 역에서든 다른 모든 역으로 이동할 수 있어야 한다.

이 조건을 만족하도록 필요한 만큼 선로를 재건설할 수 있다. 재건설은 선택한 선로 하나의 너비를 1 늘리거나 1 줄이는 것이다. 비용은 1이다. 단, 너비가 1인 선로는 더 줄일 수 없다.

각 철도 회사를 유치하는 데 드는 최소 비용을 구하라.

입력은 다음 형식으로 주어진다.

N M
A_1 B_1 W_1
A_2 B_2 W_2
...
A_M B_M W_M
Q
X_1
X_2
...
X_Q

$Q$개의 줄을 출력한다. $j$번째 줄에는 철도 회사 $j$를 유치하는 데 드는 최소 비용을 출력한다.

• $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$).
• 어느 역에서든 철도 선로를 따라 다른 모든 역으로 이동할 수 있다.
• $1 \le X_j \le 10^9$ ($1 \le j \le Q$).
• $X_j < X_{j+1}$ ($1 \le j \le Q-1$).