#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#define int long long
typedef long long llong;
const int MAXN = 500 + 10;
const int MAXM = 100000 + 10;
const int MAXQ = 1000000 + 10;
int n, m, q;
struct Edge
{
int u, v, cost;
friend bool operator < (const Edge &a, const Edge &b)
{
return a.cost < b.cost;
}
};
Edge e[MAXM];
int queries[MAXQ];
llong answer[MAXQ];
std::vector <std::pair <int,int>> g[MAXN];
int leftMAX[MAXM];
int rightMIN[MAXM];
int startT[MAXM];
int endT[MAXM];
int edge[MAXM];
int par[MAXN];
void addEdge(int u, int v, int idx)
{
g[u].push_back({v, idx});
g[v].push_back({u, idx});
}
void removeEdge(int u, int v)
{
for (auto &x : g[u])
{
if (x.first == v)
{
std::swap(x, g[u].back());
g[u].pop_back();
break;
}
}
for (auto &x : g[v])
{
if (x.first == u)
{
std::swap(x, g[v].back());
g[v].pop_back();
break;
}
}
}
void rebuildDFS(int node)
{
for (const auto &[u, idx] : g[node])
{
if (u == par[node])
{
continue;
}
par[u] = node;
edge[u] = idx;
rebuildDFS(u);
}
}
bool vis[MAXN];
int findLCA(int u, int v)
{
std::fill(vis + 1, vis + 1 + n, false);
int node = v;
while (node != 0)
{
vis[node] = true;
node = par[node];
}
node = u;
while (!vis[node])
{
node = par[node];
}
return node;
}
int findChainMAX(int u, int v)
{
if (u == v) return 0;
int res = findChainMAX(par[u], v);
if (res == 0 || edge[u] > edge[res]) return u;
else return res;
}
int findChainMIN(int u, int v)
{
if (u == v) return 0;
int res = findChainMIN(par[u], v);
if (res == 0 || edge[u] < edge[res]) return u;
else return res;
}
int findMAX(int u, int v)
{
int lca = findLCA(u, v);
int resU = findChainMAX(u, lca);
int resV = findChainMAX(v, lca);
if (resU == 0 || (resV != 0 && edge[resV] > edge[resU])) return resV;
else return resU;
}
int findMIN(int u, int v)
{
int lca = findLCA(u, v);
int resU = findChainMIN(u, lca);
int resV = findChainMIN(v, lca);
if (resU == 0 || (resV != 0 && edge[resV] < edge[resU])) return resV;
else return resU;
}
llong addToSum[MAXQ];
llong addToTimes[MAXQ];
int firstBiggerQuery(int val)
{
int l = 0, r = q + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (queries[mid] < val) l = mid;
else r = mid;
}
return r;
}
void solve()
{
std::sort(e + 1, e + 1 + m);
for (int i = 1 ; i <= n ; ++i)
{
g[i].clear();
}
for (int i = 1 ; i < n ; ++i)
{
g[i].push_back({i + 1, 0});
g[i + 1].push_back({i, 0});
}
par[1] = 0;
edge[1] = m + 1;
rebuildDFS(1);
for (int i = 1 ; i <= m ; ++i)
{
int res = findMIN(e[i].u, e[i].v);
assert(res > 1 && res <= n);
leftMAX[i] = edge[res];
removeEdge(res, par[res]);
addEdge(e[i].u, e[i].v, i);
par[1] = 0;
edge[1] = m + 1;
rebuildDFS(1);
}
for (int i = 1 ; i <= n ; ++i)
{
g[i].clear();
}
for (int i = 1 ; i < n ; ++i)
{
g[i].push_back({i + 1, m + 1});
g[i + 1].push_back({i, m + 1});
}
par[1] = 0;
edge[1] = 0;
rebuildDFS(1);
for (int i = m ; i >= 1 ; --i)
{
int res = findMAX(e[i].u, e[i].v);
assert(res > 1 && res <= n);
rightMIN[i] = edge[res];
removeEdge(res, par[res]);
addEdge(e[i].u, e[i].v, i);
par[1] = 0;
edge[1] = 0;
rebuildDFS(1);
}
for (int i = 1 ; i <= m ; ++i)
{
if (leftMAX[i] == 0)
{
startT[i] = 1;
} else
{
startT[i] = (e[i].cost + e[leftMAX[i]].cost + 2) / 2;
}
if (rightMIN[i] == m + 1)
{
endT[i] = 1e9;
} else
{
endT[i] = (e[rightMIN[i]].cost + e[i].cost) / 2;
}
}
for (int i = 1 ; i <= m ; ++i)
{
int l = firstBiggerQuery(startT[i]);
int mid = firstBiggerQuery(e[i].cost);
int r = firstBiggerQuery(endT[i] + 1);
addToSum[l] += e[i].cost;
addToSum[mid] += -2 * e[i].cost;
addToSum[r] += e[i].cost;
addToTimes[l] += -1;
addToTimes[mid] += 2;
addToTimes[r] += -1;
}
llong times = 0;
llong sum = 0;
for (int i = 1 ; i <= q ; ++i)
{
sum += addToSum[i];
times += addToTimes[i];
answer[i] = times * queries[i] + sum;
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << answer[i] << '\n';
}
}
void input()
{
std::cin >> n >> m;
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> e[i].u >> e[i].v >> e[i].cost;
}
std::cin >> q;
for (int i = 1 ; i <= q ; ++i)
{
std::cin >> queries[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
signed main()
{
fastIOI();
input();
solve();
print();
return 0;
}
/*
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
1
3
6
8
10
13
17
*/
