#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
using namespace std;
typedef long long ll;
// ----- Edge structure -----
struct Edge {
int u, v;
ll w;
int id; // original id (0-indexed)
};
// ----- Global Variables -----
int N, M;
vector<Edge> edges; // original edges
// We'll compute Lbound and Rbound for each edge (indexed by its original id)
vector<ll> Lbound, Rbound;
// ----- DFS in Tree T -----
// T is maintained as an adjacency list: for each node, a list of (neighbor, edge id)
bool dfsPath(int cur, int target, int parent, vector<int> &path) {
if(cur == target) return true;
for(auto &p : path); // dummy
// We'll pass T as a global reference below.
return false;
}
// We'll write a DFS that finds the unique path from 's' to 't' in tree T.
// It stores in 'path' the edge ids (from T) on the path.
bool findPath(int cur, int target, int parent, const vector<vector<pair<int,int>>>& T, vector<int> &path) {
if(cur == target) return true;
for(auto &pr : T[cur]) {
int nxt = pr.first, edgeId = pr.second;
if(nxt == parent) continue;
if(findPath(nxt, target, cur, T, path)) {
path.push_back(edgeId);
return true;
}
}
return false;
}
// ----- Lower Bound Computation -----
// Process edges in increasing order. Maintain tree T as an undirected spanning tree (as an adjacency list).
// For each edge (in sorted order) with endpoints u and v:
// - If u and v are not connected in T (found by DFS), then set Lbound = 1 and add the edge into T.
// - Otherwise, find the unique path in T between u and v, let j be the edge on that path with maximum weight.
// Then set Lbound = (w_i + w_j) / 2 + 1.
// Also, if w_i < w_j, then remove edge j from T and add edge i.
void computeLowerBounds() {
Lbound.assign(M, 0);
// T: tree maintained as adjacency list; T[node] = vector of (neighbor, edge id)
vector<vector<pair<int,int>>> T(N);
// Sort edges in increasing order by weight.
vector<Edge> sorted = edges;
sort(sorted.begin(), sorted.end(), [](const Edge &a, const Edge &b){
return a.w < b.w;
});
// For connectivity checking we use DFS in T.
auto connected = [&](int s, int t) -> bool {
vector<bool> vis(N, false);
function<bool(int)> dfs = [&](int cur) -> bool {
if(cur == t) return true;
vis[cur] = true;
for(auto &pr : T[cur]) {
int nxt = pr.first;
if(!vis[nxt] && dfs(nxt))
return true;
}
return false;
};
return dfs(s);
};
// For each edge in sorted order, process it.
for(auto &e : sorted) {
int u = e.u, v = e.v;
if(!connected(u, v)) {
// Not connected: edge e is critical for small X.
Lbound[e.id] = 0;
// Add e to T:
T[u].push_back({v, e.id});
T[v].push_back({u, e.id});
} else {
// u and v are already connected in T.
// Find the unique path from u to v in T.
vector<int> pathEdgeIds;
findPath(u, v, -1, T, pathEdgeIds);
// The path is stored in reverse order; we scan all edge ids in the path.
int maxEdgeId = -1;
ll minW = 1e18;
for (int id : pathEdgeIds) {
ll wtemp = edges[id].w; // original weight of that edge.
if(wtemp < minW) { minW = wtemp; maxEdgeId = id; }
}
// Compute lower bound for current edge:
// According to the idea: L_val = (w_i + w_j) / 2 + 1.
Lbound[e.id] = (e.w + minW) / 2 + 1;
// Additionally, if current edge is strictly lighter than the one on the path,
// then we can replace that heavier edge in T with the current edge.
// Remove edge maxEdgeId from T.
int a = edges[maxEdgeId].u, b = edges[maxEdgeId].v;
auto removeEdge = [&](int x, int y, int eid) {
for(auto it = T[x].begin(); it != T[x].end(); ++it) {
if(it->first == y && it->second == eid) {
T[x].erase(it);
break;
}
}
};
removeEdge(a, b, maxEdgeId);
removeEdge(b, a, maxEdgeId);
// Add current edge e instead.
T[u].push_back({v, e.id});
T[v].push_back({u, e.id});
}
}
}
// ----- Upper Bound Computation -----
// Process edges in decreasing order. We use a similar procedure, maintaining a spanning tree T.
// For each edge (in descending order) with endpoints u and v:
// - If not connected in T, then Rbound = 10^9.
// - Otherwise, find the unique path and let k be the edge with maximum weight on the path.
// Set Rbound = (w_i + w_k) / 2.
// Also, if w_i < w_k, then replace that edge in T by the current edge.
void computeUpperBounds() {
Rbound.assign(M, 0);
vector<vector<pair<int,int>>> T(N);
vector<Edge> sorted = edges;
sort(sorted.begin(), sorted.end(), [](const Edge &a, const Edge &b){
return a.w > b.w; // descending order.
});
auto connected = [&](int s, int t) -> bool {
vector<bool> vis(N, false);
function<bool(int)> dfs = [&](int cur) -> bool {
if(cur == t) return true;
vis[cur] = true;
for(auto &pr : T[cur]) {
int nxt = pr.first;
if(!vis[nxt] && dfs(nxt))
return true;
}
return false;
};
return dfs(s);
};
for(auto &e : sorted) {
int u = e.u, v = e.v;
if(!connected(u, v)) {
// Not connected: edge is used for very large X.
Rbound[e.id] = 1000000001LL;
T[u].push_back({v, e.id});
T[v].push_back({u, e.id});
} else {
vector<int> pathEdgeIds;
findPath(u, v, -1, T, pathEdgeIds);
int maxEdgeId = -1;
ll maxW = -1;
for (int id : pathEdgeIds) {
ll wtemp = edges[id].w;
if(wtemp > maxW) { maxW = wtemp; maxEdgeId = id; }
}
Rbound[e.id] = (e.w + maxW) / 2; // note: floor division.
int a = edges[maxEdgeId].u, b = edges[maxEdgeId].v;
auto removeEdge = [&](int x, int y, int eid) {
for(auto it = T[x].begin(); it != T[x].end(); ++it) {
if(it->first == y && it->second == eid) {
T[x].erase(it);
break;
}
}
};
removeEdge(a, b, maxEdgeId);
removeEdge(b, a, maxEdgeId);
T[u].push_back({v, e.id});
T[v].push_back({u, e.id});
}
}
}
// ----- Main -----
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
edges.resize(M);
for (int i = 0; i < M; i++){
int u, v; ll w;
cin >> u >> v >> w;
u--; v--; // convert to 0-indexed
edges[i] = {u, v, w, i};
}
Lbound.resize(M); Rbound.resize(M);
computeLowerBounds();
computeUpperBounds();
// (For debugging, you may print each edge's interval:)
// for (int i = 0; i < M; i++){
// cout << "Edge " << i+1 << " (w=" << edges[i].w << "): [" << Lbound[i] << ", " << Rbound[i] << "]\n";
// }
// Answer queries.
// For each query X, the MST chosen is exactly the set of edges i for which X is in [Lbound[i], Rbound[i]].
// The cost is sum_{i with X in [L_i,R_i]} |w_i - X|.
int Q; cin >> Q;
vector<pli> AA, BB;
for(int i=0;i<M;i++){
AA.pb({Lbound[i],-1});
AA.pb({edges[i].w+1,2});
AA.pb({Rbound[i]+1,-1});
BB.pb({Lbound[i],edges[i].w});
BB.pb({edges[i].w+1,-2*edges[i].w});
BB.pb({Rbound[i]+1,edges[i].w});
}
sort(all(AA));
sort(all(BB));
vc<ll>SA(si(AA)), SB(si(AA));
rep(i,si(AA)){
SA[i] = AA[i].se;
SB[i] = BB[i].se;
if(i) SA[i]+=SA[i-1], SB[i]+=SB[i-1];
}
while(Q--){
ll X; cin >> X;
ll totalCost = 0;
int pv = lower_bound(all(AA),pli(X+1,-5)) - AA.begin(); pv--;
cout << SA[pv] * X + SB[pv] << "\n";
}
return 0;
}
