#include <bits/stdc++.h>
#define all(vin) vin.begin(), vin.end()
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, m, q, _x[N], _y[N], _c[N], A[N];
namespace sub4{
int pa[N], sz[N];
int fin(int u){
return pa[u] == u ? u : pa[u] = fin(pa[u]);
}
bool dsu(int u,int v){
u = fin(u);
v = fin(v);
if(u == v) return 0;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
pa[v] = u;
return 1;
}
int le[N], ri[N], pt[N];
ll kq[N];
vector<int> rrh;
void solve(){
for(int i = 1; i <= m; i ++) rrh.push_back(_c[i]);
sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
for(int k = 1; k <= (int)rrh.size(); k ++){
int tmp = rrh[k - 1];
pt[k] = rrh[k - 1];
vector<pair<int,int>> edge;
ll ans = 0;
for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i ++){
edge.push_back({abs(_c[i] - tmp), i});
}
sort(all(edge));
for(auto [wt, id] : edge){
if(dsu(_x[id], _y[id])){
le[k] += (_c[id] <= tmp);
ri[k] += (_c[id] >= tmp);
kq[k] += wt;
// cerr << id << " " << _x[id] << " " << _y[id] << " " << _c[id] << " r\n";
}
}
// cerr << " " << k << " " << tmp << " " << kq[k] << " " << le[k] << " " << ri[k] << " t\n";
}
int ptr = 0, lag = (int)rrh.size();
for(int k = 1; k <= q; k ++){
while(ptr < lag && pt[ptr + 1] < A[k]) ptr++;
if(!ptr){
int i = ptr + 1;
cout << kq[i] + 1ll * ri[i] * (pt[i] - A[k]) << "\n";
continue;
}
if(ptr == lag){
int i = ptr;
cout << kq[ptr] + 1ll * le[i] * (A[k] - pt[ptr]) << "\n";
continue;
}
ll B = kq[ptr] + 1ll * le[ptr] * (A[k] - pt[ptr]) - 1ll * (n - 1 - le[ptr]) * (A[k] - pt[ptr]);
ll C = kq[ptr + 1] + 1ll * ri[ptr + 1] * (pt[ptr + 1] - A[k]) - 1ll * (n - 1 - ri[ptr + 1]) * (pt[ptr + 1] - A[k]);
// cerr << B << " " << C << " r\n";
cout << min(B, C) << "\n";
}
}
}
/*
4 6
1 2 2
2 3 16
3 4 3
3 4 3
2 4 13
1 3 7
5
5 7 8 8 10
*/
namespace sub3{
vector<int> vr[N];
ll st[N << 2], lz[N << 2], T[N << 2];
void dolz(int i){
if(!lz[i]) return;
int x = lz[i]; lz[i] = 0;
lz[i << 1] += x;
lz[i << 1|1] += x;
st[i << 1] += x;
st[i << 1|1] += x;
T[i << 1] += T[i];
T[i << 1|1] += T[i];
T[i] = 0;
}
void update(int i,int l,int r,int u,int v,int val,int type){
if(l > r || r < u || v < l) return;
if(u <= l && r <= v){
st[i] += val;
T[i] += type;
lz[i] += val;
return;
}
dolz(i);
int mid = (l + r) / 2;
update(i << 1, l, mid, u, v, val, type);
update(i << 1|1, mid + 1, r, u, v, val, type);
}
int idx[N];
int get(int i,int l,int r,int u){
if(l > r || r < u || u < l) return 0;
if(l == r){
idx[u] = i;
return st[i];
}
dolz(i);
int mid = (l + r) / 2;
return get(i << 1, l, mid, u) + get(i << 1|1, mid + 1, r, u);
}
void solve(){
sort(A + 1, A + q + 1);
for(int i = 1; i <= m; i ++){
vr[_x[i]].push_back(_c[i]);
}
for(int i = 1; i < n; i ++){
sort(all(vr[i]));
for(int j = 0; j < vr[i].size(); j ++){
if(!j){
int pos = upper_bound(A + 1, A + q + 1, vr[i][j] - 1) - A - 1;
if(pos >= 1){
update(1, 1, q, 1, pos, vr[i][j], 0);
}
continue;
}
int pre = vr[i][j - 1];
int x = vr[i][j];
int mid = (x + pre) / 2;
int _right = upper_bound(A + 1, A + q + 1, mid) - A - 1;
int _left = lower_bound(A + 1, A + q + 1, pre) - A;
if(_left <= _right) update(1, 1, q, _left, _right, -pre, 1);
_right = upper_bound(A + 1, A + q + 1, x) - A - 1;
_left = lower_bound(A + 1, A + q + 1, mid + 1) - A;
if(_left <= _right) update(1, 1, q, _left, _right, x, 0);
}
int pos = lower_bound(A + 1, A + q + 1, vr[i].back() + ((int)vr[i].size() > 1)) - A;
if(pos <= q){
update(1, 1, q, pos, q, -vr[i].back(), 1);
}
}
for(int i = 1; i <= q; i ++){
int val = get(1, 1, q, i);
int pos = idx[i];
cout << val + T[pos] * A[i] - (n - 1 - T[pos]) * A[i] << "\n";
}
}
}
namespace sub2{
int pa[N], sz[N];
int fin(int u){
return pa[u] == u ? u : pa[u] = fin(pa[u]);
}
bool dsu(int u,int v){
u = fin(u);
v = fin(v);
if(u == v) return 0;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
pa[v] = u;
return 1;
}
void solve(){
for(int k = 1; k <= q; k ++){
vector<tuple<int,int,int>> edge;
ll ans = 0;
for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i ++){
edge.push_back({abs(_c[i] - A[k]), _x[i], _y[i]});
}
sort(all(edge));
for(auto [val, x, y] : edge){
if(dsu(x, y)) ans += val;
}
cout << ans << "\n";
}
}
}
namespace sub1{
#define int long long
bool flag[N];
vector<int> p[N];
void solve(){
for(int k = 1; k <= q; k ++){
int ans = 1e18;
for(int msk = 0; msk < (1 << m); msk ++){
for(int i = 1; i <= n; i ++){
flag[i] = 0;
p[i].clear();
}
int cnt = 0;
for(int i = 1; i <= m; i ++) if(msk >> (i - 1) & 1){
int x = _x[i];
int y = _y[i];
p[x].push_back(y);
p[y].push_back(x);
cnt += abs(_c[i] - A[k]);
}
queue<int> q;
q.push(1);
flag[1] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
for(auto j : p[u]) if(!flag[j]){
q.push(j);
flag[j] = 1;
}
}
bool ff = true;
for(int i = 1; i <= n; i ++) if(!flag[i]){
ff = false;
break;
}
if(ff) ans = min(ans, cnt);
}
cout << ans << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "repj"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> m;
bool ff = true;
for(int i = 1; i <= m; i ++){
cin >> _x[i] >> _y[i] >> _c[i];
if(_y[i] != _x[i] + 1) ff = false;
}
cin >> q;
for(int i = 1; i <= q; i ++) cin >> A[i];
if(m <= 16 && q <= 10) sub1 :: solve();
else if(q <= 10) sub2 :: solve();
else if(ff) sub3 :: solve();
else sub4 :: solve();
}
