#include<bits/stdc++.h>
#define int long long 
#define Maxn 3005 
using namespace std;
int n,m,cnt,s,t;
int U[Maxn],V[Maxn],W[Maxn],color[Maxn];
int s1[Maxn],s2[Maxn],tot;
vector<int> parth[Maxn];
vector<pair<int,int> > q[Maxn];
int lin[Maxn<<1],to[Maxn<<1],val[Maxn<<1],h[Maxn],now[Maxn];
int Q[Maxn],dis[Maxn];
int road[Maxn][20],f[Maxn][20],dep[Maxn];
void add(int x,int y,int z) {
	lin[++cnt] = h[x];
	to[cnt] = y;
	val[cnt] = z;
	h[x] = cnt;
}
int value(int x = s,int low = LONG_LONG_MAX) {
	if(x == t)return low;
	int res = 0;
	for(int i=now[x];i&&low>res;i=lin[i]) {
		int u = to[i]; now[x] = i;
		if(dis[u] == dis[x]+1&&val[i]) {
			int num = value(u,min(low-res,val[i]));
			if(!num)continue;
			val[i] -= num,val[i^1] = num;
			res += num;
		}
	} return res;
}
bool bfs(int op) {
	for(int u:parth[op])
		dis[u] = 0;
	Q[0] = s;
	dis[s] = 1; now[s] = h[s];
	int l = 0,r = 0;
	while(l <= r) {
		int x = Q[l++];
		for(int i=h[x];i;i=lin[i]) {
			int u = to[i],w = val[i];
			if(!dis[u]&&w) {
				now[u] = h[u];
				dis[u] = dis[x] + 1;
				if(u == t)return true;
				Q[++r] = u;
			}
		}
	} return false;
}
int Dinic(int op) {
	cnt = 1;
	for(int u:parth[op])
		h[u] = 0;
	for(int i=1;i<=m;i++)
		add(U[i],V[i],W[i]),
		add(V[i],U[i],W[i]);
	int ans = 0;
	while(bfs(op))ans += value();
	return ans;
}
void build(int l,int r,int op) {
	if(r-1 <= l)return ;
	s = parth[op][l],t = parth[op][r-1];
	int res = Dinic(op),q1 = 0,q2 = 0;
	q[s].push_back({t,res});
	q[t].push_back({s,res});
	for(int i=l;i<r;i++)
		if(dis[parth[op][i]])
			s1[++q1] = parth[op][i];
		else s2[++q2] = parth[op][i];
	for(int i=1;i<=q1;i++)
		parth[op][i+l-1] = s1[i];
	for(int i=1;i<=q2;i++)
		parth[op][l+q1+i-1] = s2[i];
	build(l,l+q1,op); build(l+q1,r,op);
}
void dfs(int x,int op) {
	color[x] = op;
	parth[op].push_back(x);
	for(pair<int,int> u:q[x])
		if(!color[u.first])
		dfs(u.first,op);
}
void prepare(int x,int fa) {
	f[x][0] = fa;
	dep[x] = dep[fa] + 1;
	for(auto u:q[x]) {
		if(u.first == fa)
			continue;
		road[u.first][0] = u.second;
		prepare(u.first,x); 
	}
}
void solve(int op) {
	prepare(parth[op][0],0);
	for(int i=1;i<20;i++) {
		for(int u:parth[op])
			f[u][i] = f[f[u][i-1]][i-1],
			road[u][i] = road[f[u][i-1]][i-1]+road[u][i-1];
	}
}
int Query(int u,int v) {
	int ans = 0,tot0 = 19;
	if(dep[u] < dep[v])swap(u,v);
	while(dep[u] != dep[v]) {
		while(dep[f[u][tot0]] >= dep[v])
			ans += road[u][tot0],
			u = f[u][tot0];
		tot0 --;
	} 
	tot0 = 19;
	while(f[u][0] != f[v][0]) {
		while(f[u][tot0] != f[v][tot0])
			ans += road[u][tot0]+road[v][tot0],
			u = f[u][tot0],v = f[v][tot0];
		tot0 ++;
	} return ans+road[u][0]+road[v][0];
}
signed main()
{
	int t1;
	cin>>t1;
	while(t1 --) {
		memset(f,0,sizeof(f));
		memset(road,0,sizeof(f));
		tot = cnt = 0;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			q[i].clear(),color[i] = 0;
		for(int i=1;i<=m;i++) {
			cin>>U[i]>>V[i]>>W[i];
			q[U[i]].push_back({V[i],W[i]});
			q[V[i]].push_back({U[i],W[i]});
		}
		for(int i=1;i<=n;i++)
			if(!color[i])dfs(i,++tot);
		for(int i=1;i<=n;i++)
			q[i].clear();
		for(int i=1;i<=tot;i++)
			build(0,parth[i].size(),i),
			solve(i);
		int query; cin>>query;
		while(query --) {
			int x,ans = 0; 
			cin>>x;
			for(int i=1;i<n;i++)
				for(int j=i+1;j<=n;j++)
					if(color[i] != color[j])
						ans ++;
					else if(Query(i,j) <= x)
						ans ++;
			cout<<ans<<"\n";
		}
		for(int i=1;i<=tot;i++)
			parth[i].clear();
		cout<<"\n";
	}
	return 0;
 }