#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Edge structure
struct Edge {
int u, v;
ll w;
};
// DSU structure for union-find.
struct DSU {
vector<int> parent;
DSU(int n) : parent(n) {
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int a) {
return parent[a] == a ? a : parent[a] = find(parent[a]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if(a == b) return false;
parent[b] = a;
return true;
}
};
// Main function
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
for (int i = 0; i < M; i++){
int u, v; ll w;
cin >> u >> v >> w;
u--; v--; // convert to 0-index
edges[i] = {u, v, w};
}
// Sort edges by weight in ascending order.
sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){
return a.w < b.w;
});
// For each edge, we compute its range [L_i, R_i] such that it appears in the MST (with cost function |w-X|)
// if and only if X is in that range.
// We assume the allowed X range is [1, 10^9].
const ll X_MIN = 1, X_MAX = 1000000000LL;
vector<ll> Lbound(M), Rbound(M);
for (int i = 0; i < M; i++){
// --- Compute lower bound for edge i ---
DSU dsu_lower(N);
bool connected = false;
ll L_val = X_MIN; // default: if no previous edge connects the endpoints, edge i is used for very small X.
for (int j = i - 1; j >= 0; j--){
dsu_lower.unite(edges[j].u, edges[j].v);
if(dsu_lower.find(edges[i].u) == dsu_lower.find(edges[i].v)){
// When the endpoints become connected,
// we define lower bound as the average (rounded up) of the current edge’s weight and edge j’s weight.
L_val = (edges[i].w + edges[j].w) / 2 + 1;
connected = true;
break;
}
}
Lbound[i] = L_val;
// --- Compute upper bound for edge i ---
DSU dsu_upper(N);
connected = false;
ll R_val = X_MAX; // default: if no later edge connects them, then edge i is used for very high X.
for (int j = i + 1; j < M; j++){
dsu_upper.unite(edges[j].u, edges[j].v);
if(dsu_upper.find(edges[i].u) == dsu_upper.find(edges[i].v)){
// Define upper bound as the average (rounded down) of the current edge’s weight and edge j’s weight.
R_val = (edges[i].w + edges[j].w) / 2;
connected = true;
break;
}
}
Rbound[i] = R_val;
}
// For debugging, you might print out the ranges:
// for (int i = 0; i < M; i++){
// cout << "Edge " << i+1 << " (w=" << edges[i].w << "): ["
// << Lbound[i] << ", " << Rbound[i] << "]\n";
// }
// For each query X, the MST selected is exactly the set of edges i for which X is in [Lbound[i], Rbound[i]].
// The total reconstruction cost is then:
// sum_{i: X in [Lbound[i], Rbound[i]]} |edges[i].w - 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]){
if(X >= edges[i].w)
totalCost += (X - edges[i].w);
else
totalCost += (edges[i].w - X);
}
}
cout << totalCost << "\n";
}
return 0;
}
