#include <bits/stdc++.h>
#define int long long
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
using di = pair<int, int>;
using vd = vector<di>;
template<typename A, typename B>
string to_string (pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(T x) {
string S = "[";
bool first = true;
for (const auto v: x) {
if (!first) S += ", ";
S += to_string(v);
first = false;
}
S += "]";
return S;
}
string to_string( string S ){
return S;
}
void dbg_out () {
cout << endl;
}
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
cout << to_string(H) << " ";
dbg_out(T...);
}
#ifdef DEBUG
# define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
# define dbg(...)
#endif
struct Road {
int a, b, cost;
int xr;
Road (int _a, int _b, int _cost) : a(_a), b(_b), cost(_cost) {
xr = _a ^ _b;
}
inline int next (int node) {
return xr ^ node;
}
bool operator< (const Road &other) {
return cost < other.cost;
}
};
using t_Roads = vector<Road>;
using bdata = vector<bool>;
t_Roads road_array;
igrid road_indices;
bdata isUsing;
idata visited; int stage = 1;
bool dfs (int node, int target, pair<int, int> &ans) {
if (node == target) return true;
if (visited[node] == stage) return false;
visited[node] = stage;
for (int iR : road_indices[node]) {
Road &road = road_array[iR];
int next = road.next(node);
if (dfs(next, target, ans)) {
if (road.cost < ans.first)
ans = { road.cost, iR };
return true;
}
}
return false;
}
struct UFD {
idata parents;
UFD (int size) {
parents.resize(size);
iota(parents.begin(), parents.end(), 0);
}
int boss (int x) {
if (parents[x] != x)
parents[x] = boss(parents[x]);
return parents[x];
}
void merge (int a, int b) {
a = boss(a); b = boss(b);
parents[a] = b;
}
};
signed main () {
int N, M;
cin >> N >> M;
road_indices.resize(N);
for (int i = 0; i < M; i ++) {
int a, b, c;
cin >> a >> b >> c;
a --; b --;
road_array.push_back( Road(a, b, c) );
}
sort(road_array.begin(), road_array.end());
UFD ufd(N);
isUsing.resize(M);
int cost = 0;
int slope = - (N - 1);
vd slope_modifications;
for (int i = 0; i < M; i ++) {
Road &road = road_array[i];
if (ufd.boss(road.a) == ufd.boss(road.b)) continue ;
ufd.merge(road.a, road.b);
road_indices[road.a].push_back(i);
road_indices[road.b].push_back(i);
isUsing[i] = true;
slope_modifications.push_back({ road.cost * 2, 2 });
cost += 2 * road.cost;
}
visited.resize(N);
for (int i = 0; i < M; i ++) {
if (isUsing[i]) continue ;
pair<int, int> answer = { 1e18, -1 };
Road &new_road = road_array[i];
stage ++;
if (!dfs(new_road.a, new_road.b, answer)) continue ;
Road &old_road = road_array[answer.second];
slope_modifications.push_back({ new_road.cost + old_road.cost, - 2 });
slope_modifications.push_back({ new_road.cost * 2, 2 });
road_indices[old_road.a].erase(
find(
road_indices[old_road.a].begin(),
road_indices[old_road.a].end(),
answer.second
)
);
road_indices[old_road.b].erase(
find(
road_indices[old_road.b].begin(),
road_indices[old_road.b].end(),
answer.second
)
);
road_indices[new_road.a].push_back(i);
road_indices[new_road.b].push_back(i);
}
sort(slope_modifications.begin(), slope_modifications.end());
int last = 0; int modId = 0;
int Q; cin >> Q;
for (int q = 0; q < Q; q ++) {
int t; cin >> t; t *= 2;
while (modId != slope_modifications.size() && slope_modifications[modId].first < t) {
int delta = slope_modifications[modId].first - last;
cost += slope * delta;
last += delta;
slope += slope_modifications[modId].second;
modId ++;
}
int delta = t - last;
cost += slope * delta;
last += delta;
cout << (cost >> 1) << "\n";
}
}
