#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
struct DSU {
ll connected;
vector<ll> par, sz;
stack<array<ll, 2> > st;
DSU(ll n) {
par = sz = vector<ll>(n + 1, 0);
for (ll i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
connected = n;
}
ll findparent(ll u) {
if (par[u] == u)return u;
ll parent = findparent(par[u]);
//if not rollback, uncomment
par[u] = parent;
return parent;
}
ll getsize(ll u) {
return sz[findparent(u)];
}
void unite(ll u, ll v) {
ll par1 = findparent(u), par2 = findparent(v);
st.push({-1, -1});
if (par1 == par2)
return;
if (sz[par1] > sz[par2])
swap(par1, par2);
st.pop();
st.push({connected, par1});
connected--;
sz[par2] += sz[par1];
par[par1] = par2;
}
void rollback() {
if (st.size()) {
auto x = st.top();
st.pop();
if (x[0] == -1)return;
connected = x[0];
par[x[1]] = x[1];
}
}
bool is_connected(ll u, ll v) {
return findparent(u) == findparent(v);
}
};
array<ll, 2> getS(vector<pair<ll, ll> > &a, ll x) {
ll sz = a.size(), l = 0, r = sz - 1, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
if (a[mid].first > x)r = mid - 1;
else l = mid + 1, ans = mid;
}
if (ans == -1)return {0LL, 0LL};
return {ans + 1, a[ans].second};
}
int main() {
baraa
ll n, m;
cin >> n >> m;
vector<array<ll, 3> > edges(m);
map<ll, vector<array<ll, 2> > > mp;
for (auto &[w, u, v]: edges) {
cin >> u >> v >> w;
mp[w].push_back({u, v});
}
sort(all(edges));
map<ll, vector<pair<ll, ll> > > cost;
map<ll, ll> index;
vector<ll> weights, l[m], r[m];
for (ll i = 0; i < m; i++) {
weights.push_back(edges[i][0]);
index[edges[i][0]] = i;
DSU dsu(n);
dsu.unite(edges[i][1], edges[i][2]);
l[i].push_back(i);
if (i)
for (ll idx: l[i - 1])
if (!dsu.is_connected(edges[idx][1], edges[idx][2]))
dsu.unite(edges[idx][1], edges[idx][2]), l[i].push_back(idx);
}
for (ll i = m - 1; i >= 0; i--) {
DSU dsu(n);
dsu.unite(edges[i][1], edges[i][2]);
r[i].push_back(i);
if (i + 1 < m)
for (ll idx: r[i + 1])
if (!dsu.is_connected(edges[idx][1], edges[idx][2]))
dsu.unite(edges[idx][1], edges[idx][2]), r[i].push_back(idx);
}
sort(all(weights));
weights.erase(unique(all(weights)), weights.end());
auto nxtW = [&](ll x) {
ll it = (upper_bound(all(edges), array<ll, 3>{x, -1LL, -1LL})) - edges.begin();
return it - 1;
};
ll q;
cin >> q;
while (q--) {
ll x;
cin >> x;
ll idx = max(0LL, nxtW(x)), res = 0;
DSU dsu(n);
vector<ll> cur;
for (ll j: r[idx])cur.push_back(j);
if (idx - 1 >= 0)
for (ll j: l[idx - 1])cur.push_back(j);
if (idx + 1 < m)
for (ll j: r[idx + 1])cur.push_back(j);
sort(all(cur), [&](ll a, ll b) {
return abs(edges[a][0] - x) < abs(edges[b][0] - x);
});
for (ll j: cur)
if (!dsu.is_connected(edges[j][1], edges[j][2]))
dsu.unite(edges[j][1], edges[j][2]), res += abs(edges[j][0] - x);
cout << res << nl;
}
return 0;
}
