문제
KOI국은 N개의 도시들이 M개의 기차 노선을 통해 연결된 그래프로 표현할 수 있다.
i번째 도로는 연결하는 두 도시 Ui와 Vi, 그리고 그 철도 폭 Wi로 표현된다.
당연하게도, 철도 폭이 도로마다 다르면 열차가 운행할 수 없다.
그래서 도시 간 이동할 때 KOI국의 국민들은 열차 여려 대를 환승했어야 했다.
이런 불편함을 없애기 위해 KOI국의 왕 재민이는 철도 폭을 수정하는 공사를 펼치려 한다.
각 공사는 여러 개의 노선에서 진행할 텐데, 어느 철도 노선 하나의 폭을 1 늘리거나 1 줄일 때마다 1 만큼의 비용이 든다.
재민이는 철도 폭 Xi에 대해, 모든 도시 쌍 사이를 폭이 Xi인 열차 한 대로 운행할 수 있도록 최소의 비용으로 공사를 진행하고자 한다.
총 Q개의 철도 폭에 대해 최적의 공사 비용을 각각 출력하시오.
입력
첫 줄에 도시의 개수 N(2<=N<=500)과 기차 노선의 개수 M(N-1<=M<=10^5)이 주어진다.
이후 M줄에 걸쳐 노선이 잇는 두 도시의 번호 Ui와 Vi, 그리고 각 노선의 철도 폭 Wi(1<=Wi<=10^9)가 순서대로 주어진다.
다음 줄에 목표로 하는 철도 폭의 개수 Q(1<=Q<=10^6)가 주어진다.
이후 Q줄에 걸쳐 목표 철도 폭 Xi(1<=Xi<=10^9)가 주어진다.
이때 주어진 Xi는 항상 증가한다.
Subtask 1 (3점) : M<=16, Q<=10
Subtask 2 (4점) : Q<=10
Subtask 3 (11점) : 모든 i에 대해, Ui+1=Vi 이다.
Subtask 4 (24점) : M<=1000
Subtask 5 (31점) : Q<=20000
Subtask 6 (27점) : 제한 없음
출력
각 목표 철도 폭에 대해 최적의 공사 비용을 한 줄에 하나씩 출력하시오.
예제1
510
128
1313
145
1511
153
237
2415
346
356
452
6
3
6
8
10
13
17
8
2
5
10
9
21
예제2
34
121
124
232
234
4
1
2
3
4
1
1
2
0
예제3
1020
67914727791
18771674531
35632918108
59329296846
17237501112
49303328173
26216298255
210504024991
38158236886
11010176179
89918271145
36217165898
36624543444
4970147274
89976983490
69210108505
29972711062
110564567289
37411395464
47952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946
1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711