#pragma GCC optimize ("O3,unroll-loops")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
//#define int long long
using namespace std;
using ar = array<int, 2>;
using ar4 = array<int, 3>;
const int M = 1e5 + 5, N = 1002, Q = 1e6 + 5;
const long long INF = 1e9 + 2;
int n, m;
ar4 E[M];
vector<ar4> undo, bk, Es;
vector<ar4> cfr, cbk, fr;
long long td, Wans, cnt = 0;
bool cmp(const ar4 &X, const ar4 &Y) {
return X[0] < Y[0];
}
inline 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;
}
}
inline namespace tree {
int W[N], node[N], ptr, mn, anc[N], adj[N][2], last;
vector<ar> Q[N];
bitset<N> seen;
void init() {
dsu::init();
iota(node, node + N, 0);
memset(adj, -1, sizeof adj);
ptr = n - 1;
last = INF;
}
void merge(int u, int v, int w) {
int tu = node[dsu::gpr(u)], tv = node[dsu::gpr(v)];
if (tu == tv) return;
assert(w <= last);
last = w;
dsu::merge(u, v);
node[gpr(u)] = ++ptr;
adj[ptr][0] = tu;
adj[ptr][1] = tv;
W[ptr] = w;
}
void dfs(int v) {
//cout << "DFS AT V: " << v + 1 << endl;
seen[v] = true;
FOR(i, 0, 2) if (adj[v][i] != -1) {
int u = adj[v][i];
assert(!seen[u]);
dfs(u);
dsu::merge(u, v);
anc[dsu::gpr(v)] = W[v];
}
for (auto [u, w]: Q[v]) if (seen[u])
mn = min(mn, (w + anc[gpr(u)]) / 2);
}
int get() {
dsu::init();
mn = INF;
seen = 0;
dfs(ptr);
FOR(i, 0, n) Q[i].clear();
return mn + 1;
}
}
ar4 validate(vector<ar4> &E) {
dsu::init();
ar4 del = {-1, -1, -1};
FOR(i, 0, E.size()) {
auto &[w, u, v] = E[i];
if (!dsu::merge(u, v)) {
del = E[i];
E.erase(E.begin() + i);
return del;
}
}
return del;
}
void validatefr(vector<ar4> &E) {
vector<ar4> ok;
dsu::init();
for (int i = (int) E.size() - 1; i >= 0; --i) {
auto &[w, u, v] = E[i];
if (!dsu::merge(u, v)) {
E.erase(E.begin() + i);
return;
}
}
}
void sol(auto A, bool t) {
auto &[w, u, v] = A;
if (dsu::merge(u, v)) {
Wans += (t ? w : -w);
td += (t ? -1 : +1);
(t ? cbk : cfr).push_back(A);
}
else if (t) {
tree::Q[v].push_back({u, w});
tree::Q[u].push_back({v, w});
}
else {
A[0] *= -1;
//fr.erase(find(fr.begin(), fr.end(), A));
}
}
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);
for (int i = m - 1; i >= 0; --i) {
auto &[w, u, v] = E[i];
bk.insert(lower_bound(bk.begin(), bk.end(), E[i], cmp), E[i]);
undo.push_back(validate(bk));
}
int q; cin >> q;
int p = 0, minl = -INF;
//ar3 dar vaghe ar4-e
FOR(i, 0, q) {
int x; cin >> x;
bool t = false;
while (p < m && x >= E[p][0]) {
fr.insert(lower_bound(fr.begin(), fr.end(), E[p], cmp), E[p]);
auto U = undo.back();
undo.pop_back();
bk.erase(find(bk.begin(), bk.end(), E[p]));
if (U[0] != -1)
bk.insert(lower_bound(bk.begin(), bk.end(), U, cmp), U);
++p;
t = true;
}
if (t || x >= minl) { //build_mst() (M bar hadeaksar)
assert(++cnt <= 2 * m + 50);
validatefr(fr);
dsu::init();
Wans = td = 0;
minl = INF;
cfr.clear(), cbk.clear();
int p1 = (int) fr.size() - 1, p2 = 0;
while (p1 >= 0 && p2 != bk.size()) {
if (x - fr[p1][0] < bk[p2][0] - x)
sol(fr[p1--], 0);
else
sol(bk[p2++], 1);
}
for (; p1 >= 0; p1--) sol(fr[p1], 0);
for (; p2 != bk.size(); p2++) sol(bk[p2], 1);
tree::init();
for (int i = (int) cbk.size() - 1; i >= 0; --i) {
auto &[w, u, v] = cbk[i];
tree::merge(u, v, w);
}
for (auto &A: cfr) {
auto &[w, u, v] = A;
tree::merge(u, v, w);
}
minl = tree::get();
}
cout << 1ll * td * x + Wans << '\n';
}
return 0;
}
