//#pragma GCC optimize ("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//besmellah
//accept sho :D
#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)))
#define int long long
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 4>;
using ar5 = array<int, 5>;
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, W[N], X[Q], ps[Q], L[M], R[M];
ar3 E[M];
bitset<N> seen;
vector<ar3> Es, undo, bk;
void dfsmn(int v, int p) {
seen[v] = true;
for (auto [u, w]: adj[v]) if (u != p) {
W[u] = min(W[v], w);
dfsmn(u, v);
}
}
void build() {
FOR(i, 0, n) adj[i].clear();
seen = 0;
for (auto [w, u, v, l]: Es) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
ar3 validate(vector<ar3> &E) {
sort(E.begin(), E.end());
vector<ar3> ok;
dsu::init();
ar3 del = {-1, -1, -1, -1};
for (auto [w, u, v, l]: E) {
if (dsu::merge(u, v))
ok.push_back({w, u, v, l});
else del = {w, u, v, l};
}
E = ok;
return del;
}
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(i, 0, m) {
auto [w, u, v, l] = E[i];
build();
W[u] = INF;
dfsmn(u, u);
if (seen[v])
E[i][3] = (W[v] + w + 1) / 2;
else
E[i][3] = -INF;
Es.push_back(E[i]);
validate(Es);
}
for (int i = m - 1; i >= 0; --i) {
auto [w, u, v, l] = E[i];
bk.push_back(E[i]);
undo.push_back(validate(bk));
}
int q; cin >> q;
int p = 0, minl = -INF, td, W, cnt = 0;
//ar3 dar vaghe ar4-e
vector<ar3> fr;
FOR(i, 0, q) {
int x; cin >> x;
bool t = false;
while (p < m && x >= E[p][0]) {
fr.push_back(E[p]);
fr.back()[0] *= -1;
auto U = undo.back();
undo.pop_back();
bk.erase(find(bk.begin(), bk.end(), E[p]));
if (U[0] != -1) bk.push_back(U);
//cout << "BK .push() " << U[0] << endl;
++p;
t = true;
}
if (t || x >= minl) { //build_mst() (M bar hadeaksar)
assert(++cnt <= 2 * m);
validate(fr);
dsu::init();
W = td = 0;
minl = INF;
//al = bk + fr (bt)
vector<ar5> al; //badihish
//cout <<"QUERY" << endl;
for (auto [w, u, v, l]: fr) { //w = -w
assert(w <= x);
al.push_back({x + w, v, u, l, 0});
//cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
}
//cout << "---" << endl;
for (auto [w, u, v, l]: bk) {
assert(w >= x);
al.push_back({w - x, v, u, l, 1});
//cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
}
//
//cout << "---" << endl;
//int ans = 0;
sort(al.begin(), al.end(), [&](const auto &X, const auto &Y) {return X[0] < Y[0];});
for (auto [w, v, u, l, t]: al) {
w = (t ? w + x : x - w);
//cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
if (dsu::merge(u, v)) {
//ans += abs(w - x);
W += (t ? w : -w);
td += (t ? -1 : +1);
}
else if (t) {
minl = min(minl, l);
}
}
//cout << ans << endl;
}
cout << td * x + W << '\n';
}
return 0;
}
