#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
struct edge
{
int a;
int b;
ll w;
};
bool operator < (edge A, edge B)
{
return A.w < B.w;
}
struct costchange
{
ll w;
ll deltaX;
ll deltaC;
};
bool operator < (costchange A, costchange B)
{
return A.w < B.w;
}
const int maxM = 100'000;
const int maxN = 500;
vi A(maxM), B(maxM), W(maxM);
set<int> adj[maxN];
void addedge(int e)
{
adj[A[e]].insert(e);
adj[B[e]].insert(e);
}
void removeedge(int e)
{
adj[A[e]].erase(e);
adj[B[e]].erase(e);
}
vi vis; //done
vi cyclic; //done
vi st; //done
vi paredge;
bool discovered;
void dfs(int u, int pe)
{
// cerr << "\n\n\n\n";
// cerr << "enter : dfs " << u << ' ' << p << '\n';
vis[u] = 1;
st.push_back(u);
for(int e : adj[u])
{
// cerr << "enter edge\n";
int v = A[e] + B[e] - u;
// cerr << u << " -> " << v << '\n';
if(e == pe)
{
// cerr << "case 1\n";
continue;
}
else if(vis[v])
{
if(!discovered)
{
discovered = 1;
// cerr << "case 2\n";
// cerr << "paredge v = " << paredge[v] << '\n';
// for(int f : st) cerr << "f = " << f << " : " << paredge[f] << '\n';
for(int k = sz(st) - 1; k >= 0 && st[k] != v; k--)
{
// cerr << "checking : k = " << k << '\n';
// if(paredge[st[k]] == -1) cerr << "ATTENTION : V = " << v << '\n';
cyclic.push_back(paredge[st[k]]);
}
cyclic.push_back(e);
// cerr << "case 2 done\n";
}
}
else
{
// cerr << "case 3\n";
paredge[v] = e;
dfs(v, e);
if(discovered) return;
}
}
st.pop_back();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
// assert(M*N <= 50'000'000 - 1);
vector<edge> E(M);
for(int j = 0; j < M; j++)
{
cin >> E[j].a >> E[j].b >> E[j].w;
E[j].a--;
E[j].b--;
}
sort(E.begin(), E.end());
for(int j = 0; j < M; j++)
{
A[j] = E[j].a;
B[j] = E[j].b;
W[j] = E[j].w;
}
// cerr << "\n\n\n edges = \n";
// for(int j = 0; j < M; j++) cerr << A[j] << ' ' << B[j] << ' ' << W[j] << '\n';
// cerr << "\n\n";
for(int i = 0; i < N; i++)
adj[i].clear();
vi edgelist;
vll minW(M), maxW(M); //do 2x the actual thing!!!
for(int j = 0; j < M; j++)
{
// cerr << "\n\n\n\n\n\n\n";
// cerr << "j = " << j << '\n';
vis = vi(N, 0);
assert(sz(edgelist) < N);
// edgelist.push_back(j);
addedge(j);
// cerr << "edgelist : \n";
// for(int e : edgelist)
// cerr << A[e] << ' ' << B[e] << ' ' << W[e] << '\n';
// cerr << "###\n";
// adj = vvi(N);
// for(int e : edgelist)
// {
// adj[A[e]].push_back(e);
// adj[B[e]].push_back(e);
// }
cyclic.clear();
discovered = 0;
st.clear();
paredge = vi(N, -1);
// cerr << "done\n";
for(int i = 0; i < N; i++)
{
if(vis[i]) continue;
if(discovered) break;
dfs(i, -1);
}
// cerr << "dfs done\n";
if(cyclic.empty()) minW[j] = 0;
else
{
// cerr << "!!!!!CYCLIC DETECTED!!!!!\n";
// cerr << "case = 2" << '\n';
int mincyclic = cyclic[0];
for(int c : cyclic)
mincyclic = min(mincyclic, c);
removeedge(mincyclic);
// cerr << "# done\n";
// cerr << "mincyclic = " << mincyclic << '\n';
minW[j] = W[j] + W[mincyclic];
// cerr << "transition from " << mincyclic << " to " << j << " = " << minW[j] << "/2" << '\n';
// cerr << "3 done\n";
}
// cerr << "J = " << j << " done\n";
}
// cerr << "check\n";
// cerr << "\n\n\n\n\n\n\n\nPART 2 PART 2 PART 2\n";
// edgelist.clear();
for(int i = 0; i < N; i++)
adj[i].clear();
for(int j = M-1; j >= 0; j--)
{
// cerr << "\n\n\n\n\n\n\n";
// cerr << "j = " << j << '\n';
vis = vi(N, 0);
assert(sz(edgelist) < N);
// edgelist.push_back(j);
addedge(j);
// cerr << "edgelist : \n";
// for(int e : edgelist)
// cerr << A[e] << ' ' << B[e] << ' ' << W[e] << '\n';
// cerr << "###\n";
// adj = vvi(N);
// for(int e : edgelist)
// {
// adj[A[e]].push_back(e);
// adj[B[e]].push_back(e);
// }
cyclic.clear();
discovered = 0;
st.clear();
paredge = vi(N, -1);
// cerr << "done\n";
for(int i = 0; i < N; i++)
{
if(vis[i]) continue;
if(discovered) break;
dfs(i, -1);
}
// cerr << "dfs done\n";
if(cyclic.empty()) maxW[j] = 2'000'000'004;
else
{
// cerr << "!!!!!CYCLIC DETECTED!!!!!\n";
// cerr << "case = 2" << '\n';
// vi nwedgelist;
int maxcyclic = cyclic[0];
for(int c : cyclic)
maxcyclic = max(maxcyclic, c);
// cerr << "1 done\n";
// for(int e : edgelist)
// if(e != maxcyclic)
// nwedgelist.push_back(e);
removeedge(maxcyclic);
// cerr << "2 done\n";
// edgelist = nwedgelist;
// cerr << "# done\n";
maxW[j] = W[j] + W[maxcyclic];
// cerr << "3 done\n";
}
// cerr << "J = " << j << " done\n";
}
// for(int j = 0; j < M; j++) cerr << A[j] << ' ' << B[j] << ' ' << W[j] << " : " << minW[j] << ' ' << maxW[j] << '\n';
vector<pll> deltaX, deltaC;
for(int j = 0; j < M; j++)
{
deltaX.push_back({minW[j], -1});
deltaC.push_back({minW[j], W[j]});
deltaX.push_back({2*W[j], +1});
deltaC.push_back({2*W[j], -W[j]});
deltaX.push_back({2*W[j]+1, +1});
deltaC.push_back({2*W[j]+1, -W[j]});
deltaX.push_back({maxW[j], -1});
deltaC.push_back({maxW[j], +W[j]});
}
sort(deltaX.begin(), deltaX.end());
sort(deltaC.begin(), deltaC.end());
ll currX = 0, currC = 0;
int it = -1;
int Q;
cin >> Q;
for(int q = 0; q < Q; q++)
{
ll X;
cin >> X;
while(it+1 < sz(deltaX) && deltaX[it+1].first <= 2*X)
{
it++;
currX += deltaX[it].second;
currC += deltaC[it].second;
}
cout << currX*X + currC << '\n';
}
}
