#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
struct UnionFind {
vector<int> id;
UnionFind() {}
UnionFind(int N) { id.assign(N, -1); }
int find(int u) {
if (id[u] < 0)
return u;
return id[u] = find(id[u]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v)
return false;
if (id[u] > id[v])
swap(u, v);
id[u] += id[v];
id[v] = u;
return true;
}
};
struct Edge {
int u, v, w;
Edge() {}
Edge(int a, int b, int c) : u(a), v(b), w(c) {}
bool operator<(Edge other) const {
return tuple(w, u, v) < tuple(other.w, other.u, other.v);
};
};
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int nbSommet, nbAretes;
cin >> nbSommet >> nbAretes;
vector<Edge> edges(nbAretes);
for (auto &[u, v, w] : edges) {
cin >> u >> v >> w;
--u, --v;
}
sort(edges.begin(), edges.end());
vector<int> debRight(nbAretes), finRight(nbAretes);
vector<int> debLeft(nbAretes), finLeft(nbAretes);
vector<int> usefulEdges;
for (int iArete = nbAretes - 1; iArete >= 0; --iArete) {
UnionFind dsu(nbSommet);
int nxt = -1;
for (int i : usefulEdges) {
dsu.merge(edges[i].u, edges[i].v);
if (dsu.find(edges[iArete].u) == dsu.find(edges[iArete].v)) {
nxt = i;
break;
}
}
debRight[iArete] = edges[iArete].w + 1;
finRight[iArete] = nxt == -1 ? INF : (edges[iArete].w + edges[nxt].w) / 2;
vector<int> nxtUseful;
nxtUseful.push_back(iArete);
for (int i : usefulEdges)
if (i != nxt)
nxtUseful.push_back(i);
usefulEdges = nxtUseful;
}
usefulEdges.clear();
for (int iArete = 0; iArete < nbAretes; ++iArete) {
UnionFind dsu(nbSommet);
int nxt = -1;
for (int i : usefulEdges) {
dsu.merge(edges[i].u, edges[i].v);
if (dsu.find(edges[iArete].u) == dsu.find(edges[iArete].v)) {
nxt = i;
break;
}
}
finLeft[iArete] = edges[iArete].w;
debLeft[iArete] =
nxt == -1 ? 0 : ((edges[iArete].w + edges[nxt].w) / 2 + 1);
vector<int> nxtUseful;
nxtUseful.push_back(iArete);
for (int i : usefulEdges)
if (i != nxt)
nxtUseful.push_back(i);
usefulEdges = nxtUseful;
}
vector<tuple<int, int, int>> eventsL, eventsR;
for (int iArete = 0; iArete < nbAretes; ++iArete) {
eventsL.emplace_back(debLeft[iArete], 1, iArete);
eventsL.emplace_back(finLeft[iArete] + 1, -1, iArete);
eventsR.emplace_back(debRight[iArete], 1, iArete);
eventsR.emplace_back(finRight[iArete] + 1, -1, iArete);
}
sort(eventsL.begin(), eventsL.end());
sort(eventsR.begin(), eventsR.end());
int mult = 0, add = 0;
int posL = 0, posR = 0;
int nbRequetes;
cin >> nbRequetes;
for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
int x;
cin >> x;
while (posL < (int)eventsL.size() and get<0>(eventsL[posL]) <= x) {
auto [d, delta, iArete] = eventsL[posL++];
if (delta == 1)
mult--, add += edges[iArete].w;
else
mult++, add -= edges[iArete].w;
}
while (posR < (int)eventsR.size() and get<0>(eventsR[posR]) <= x) {
auto [d, delta, iArete] = eventsR[posR++];
if (delta == 1)
mult++, add -= edges[iArete].w;
else
mult--, add += edges[iArete].w;
}
cout << x * mult + add << '\n';
}
}
