#include <bits/stdc++.h>
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] = 1;
// 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] = 1000000000LL;
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;
while(Q--){
ll X; cin >> X;
ll totalCost = 0;
for (int i = 0; i < M; i++){
if(Lbound[i] <= X && X <= Rbound[i]){
totalCost += (X >= edges[i].w ? (X - edges[i].w) : (edges[i].w - X));
}
}
cout << totalCost << "\n";
}
return 0;
}
