#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target("avx2")
//besmellah
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ers(v, X) adj[v].erase(find(adj[v].begin(), adj[v].end(), (X)))
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;
const int M = 1e5 + 5, N = 505, Q = 1e6 + 5;
const long long INF = 1ll << 30;
namespace dsu {
int dpr[N];
void init() {
memset(dpr, -1, sizeof dpr);
}
int gpr(int x) {
return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
}
bool merge(int u, int v) {
u = gpr(u), v = gpr(v);
if (u == v) return false;
if (dpr[u] < dpr[v]) swap(u, v);
dpr[v] += dpr[u];
dpr[u] = v;
return true;
}
}
vector<ar> adj[N];
int n, m;
ar3 W[N], E[M], hame[2 * N];
bitset<N> seen;
void dfs(int v, int p) {
seen[v] = true;
for (auto [u, w]: adj[v]) if (u != p) {
W[u] = max(W[v], {w, u, v});
dfs(u, v);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
FOR(i, 0, m) {
cin >> E[i][1] >> E[i][2] >> E[i][0];
--E[i][1], --E[i][2];
if (E[i][1] > E[i][2]) swap(E[i][1], E[i][2]);
}
sort(E, E + m);
vector<ar3> undo;
deque<ar3> Es;
for (int i = m - 1; i >= 0; i--) { //ino mishe behtar kard ba DSU vali halesh nist (orderesham ye log kamtar dare)
auto [w, u, v] = E[i];
W[u] = {-INF, u, u};
seen = 0;
dfs(u, u);
if (seen[v]) {
auto [dw, du, dv] = W[v];
if (du > dv) swap(du, dv);
ers(du, (ar{dv, dw}));
ers(dv, (ar{du, dw}));
Es.erase(find(Es.begin(), Es.end(), ar3{dw, du, dv}));
//cout << "DELETING " << du + 1 << ' ' << dv + 1 << " " << dw << endl;
undo.push_back({dw, du, dv});
}
else
undo.push_back({-1, -1, -1});
//cout << "ADDING " << u + 1 << ' ' << v + 1 << ' ' << w << endl;
Es.push_back(E[i]);
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
//for (auto [w, u, v]: Es) cout << u << ' ' << v << ' ' << w << endl;
//now MST at zero
vector<ar3> jelo;
//be zaman ahamiat nemidaham
int q; cin >> q; int p = 0;
while (q--) {
int x; cin >> x;
bool t = false;
while (p < m && E[p][0] < x) { //ino hesesh bood vali log ziad dare
jelo.push_back(E[p]);
t = true;
Es.erase(find(Es.begin(), Es.end(), E[p]));
auto akh = undo.back();
undo.pop_back();
if (akh[0] != -1) Es.push_back(akh);
++p;
sort(Es.begin(), Es.end());
}
if (t) {
vector<ar3> ok;
ok.reserve(jelo.size());
dsu::init();
sort(jelo.rbegin(), jelo.rend());
for (auto [w, u, v]: jelo) if (dsu::merge(u, v)) ok.push_back({w, u, v});
jelo = ok;
}
//jelo -> small to large (x - w)
//Es -> small to large (x - w)
int p1 = 0, p2 = 0;
while (p1 != jelo.size() || p2 != Es.size()) {
if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x)))
hame[p1 + p2] = jelo[p1], ++p1;
else
hame[p1 + p2] = Es[p2], ++p2;
}
dsu::init();
long long ans = 0;
int cnt = 0;
FOR(i, 0, p1 + p2) {
auto [w, u, v] = hame[i];
w = abs(x - w);
if (dsu::merge(u, v)) {
ans += w;
++cnt;
if (cnt == n - 1) break;
}
}
cout << ans << '\n';
}
return 0;
}
