#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, w;
bool operator<(const edge &r) const {
if (w != r.w) {
return w < r.w;
}
if (u != r.u) {
return u < r.u;
}
return v < r.v;
}
};
class tree {
int n;
vector<set<pair<int, int>>> adj;
public:
tree(int n) : n(n), adj(n) {}
void link(int u, int v, int w) {
adj[u].insert({v, w});
adj[v].insert({u, w});
}
void cut(int u, int v, int w) {
adj[u].erase({v, w});
adj[v].erase({u, w});
}
vector<edge> path(int u, int v) {
vector<edge> stk;
auto dfs = [&](auto &&self, int u, int p) {
if (u == v) {
return true;
}
for (auto &[i, w] : adj[u]) {
if (i == p) {
continue;
}
stk.push_back({u, i, w});
if (self(self, i, u)) {
return true;
}
stk.pop_back();
}
return false;
};
dfs(dfs, u, 0);
return stk;
}
};
class dsu {
int n;
vector<int> par;
public:
dsu(int n) : n(n), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
void merge(int u, int v) {
u = root(u), v = root(v);
if (u != v) {
par[v] = u;
}
}
};
int main() {
int n, m;
cin >> n >> m;
vector<edge> edges(m);
for (auto &[u, v, w] : edges) {
cin >> u >> v >> w;
}
sort(edges.begin(), edges.end());
// store timestamp, {<add>}, {<rem>}
vector<pair<int, pair<vector<edge>, vector<edge>>>> forw;
tree tr(n + 1);
for (auto &[u, v, w] : edges) {
auto p = tr.path(u, v);
if (p.empty()) {
forw.push_back({w, {{{u, v, w}}, {}}});
tr.link(u, v, w);
continue;
}
edge it = *min_element(p.begin(), p.end());
if (w <= it.w) {
continue;
}
tr.cut(it.u, it.v, it.w);
tr.link(u, v, w);
forw.push_back({w, {{{u, v, w}}, {it}}});
}
vector<pair<int, pair<vector<edge>, vector<edge>>>> back;
set<edge> mstr;
tr = tree(n + 1);
reverse(edges.begin(), edges.end());
for (auto &[u, v, w] : edges) {
auto p = tr.path(u, v);
if (p.empty()) {
back.push_back({w, {{}, {{u, v, w}}}});
mstr.insert({min(u, v), max(u, v), w});
tr.link(u, v, w);
continue;
}
edge it = *max_element(p.begin(), p.end());
if (w >= it.w) {
continue;
}
tr.cut(it.u, it.v, it.w);
tr.link(u, v, w);
mstr.erase({min(it.u, it.v), max(it.u, it.v), it.w});
mstr.insert({min(u, v), max(u, v), w});
back.push_back({w, {{it}, {{u, v, w}}}});
}
set<edge> mstl;
reverse(forw.begin(), forw.end());
auto apply_add_rem = [&](pair<vector<edge>, vector<edge>> &p, set<edge> &st) {
auto &[add, rem] = p;
for (auto p : rem) {
st.erase({min(p.u, p.v), max(p.u, p.v), p.w});
}
for (auto &p : add) {
st.insert({min(p.u, p.v), max(p.u, p.v), p.w});
}
};
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
// everything <= x => mstl, > x => mstr
while (!forw.empty() && forw.back().first <= x) {
apply_add_rem(forw.back().second, mstl);
forw.pop_back();
}
while (!back.empty() && back.back().first <= x) {
apply_add_rem(back.back().second, mstr);
back.pop_back();
}
dsu dsu(n + 1);
int64_t ans = 0;
vector<edge> st;
for (auto &p : mstl) {
st.push_back(p);
}
for (auto &p : mstr) {
st.push_back(p);
}
sort(st.begin(), st.end(), [&](edge &a, edge &b) { return abs(x - a.w) < abs(x - b.w); });
for (auto &[u, v, w] : st) {
if (dsu.root(u) == dsu.root(v)) {
continue;
}
dsu.merge(u, v);
ans += abs(x - w);
}
cout << ans << '\n';
}
}
