全WA

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=155,M=6003;
int uu[M],vv[M],ww[M];
int n,m;
int head1[N],head2[N],cnt1=1,cnt2;
struct node{
	int to,w,nex;
}e1[M],e2[M];
void add1(int u,int v,int ww){
	cnt1++;e1[cnt1].to=v;e1[cnt1].nex=head1[u];e1[cnt1].w=ww;head1[u]=cnt1;
}
void add2(int u,int v,int ww){
	cnt2++;e2[cnt2].to=v;e2[cnt2].nex=head2[u];e2[cnt2].w=ww;head2[u]=cnt2;
}
int deep[N],noww[N];
int s,t;
bool bfs(){
	queue<int>q;
	q.push(s);
	for(int i=1;i<=n;i++)deep[i]=0;
	deep[s]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
//		cout<<x<<endl;
		noww[x]=head1[x];
		for(int i=head1[x];i;i=e1[i].nex){
			int y=e1[i].to;
			if(e1[i].w==0)continue;
			if(deep[y]!=0)continue;
			deep[y]=deep[x]+1;
			q.push(y);
		}
	} 
	return deep[t]!=0;
}
ll dfs(int x,int summ){
	int us=0,tmp;
	if(x==t)return summ;
	for(int i=head1[x];i;i=e1[i].nex){
		int y=e1[i].to;
		if(deep[y]!=deep[x]+1)continue;
		if(e1[i].w==0)continue;
		tmp=dfs(y,min(summ,e1[i].w));
		e1[i].w-=tmp;
		e1[i^1].w+=tmp;
		us+=tmp;
		summ-=tmp;
		if(tmp==0)deep[y]=0;
		if(summ==0){
			deep[x]=0;break;
		}
	}
	return us;
}
int ans;
void dinic(){
	cnt1=1;
	ans=0;
	memset(head1,0,sizeof(head1));
	for(int i=1;i<=m;i++){
		add1(uu[i],vv[i],ww[i]);add1(vv[i],uu[i],ww[i]);
	}
//	cout<<12345;
	while(bfs()){
//		cout<<1;
		ans+=dfs(s,12345678);
	}
}
void build(vector<int>&a){
//	for(int i:a)cout<<i<<' ';
//	cout<<endl;
	if(a.size()<=1)return;
	s=a[0],t=a[1];
	dinic();
	add2(s,t,ans);add2(t,s,ans);
	vector<int>l,r;
	for(int i:a){
		if(deep[i])l.push_back(i);
		else r.push_back(i);
	}
	build(l);build(r);
}
int dis[N];
int work(int u,int v){
	memset(dis,0,sizeof(dis));
	dis[u]=12345678;
	queue<int>q;q.push(u);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head2[x];i;i=e2[i].nex){
			int y=e2[i].to;
			if(dis[y])continue;
			dis[y]=min(dis[x],e2[i].w+1);
			q.push(y);
		}
	}
	return dis[v]-1;
}
int tt;
ll so[N*N],tot;
int main(){
	read(tt);
	while(tt--){
		memset(e1,0,sizeof(e1));memset(e2,0,sizeof(e2));
		memset(head1,0,sizeof(head1));memset(head2,0,sizeof(head2));cnt1=1;cnt2=0;
		memset(uu,0,sizeof(uu));memset(vv,0,sizeof(vv));memset(ww,0,sizeof(ww));
		ans=0;memset(deep,0,sizeof(deep));memset(noww,0,sizeof(noww));memset(dis,0,sizeof(dis));
		read(n);read(m);
		for(int i=1;i<=m;i++){
			read(uu[i]);read(vv[i]);read(ww[i]);
		}
		vector<int>g;
		for(int i=1;i<=n;i++)g.push_back(i);
		build(g);
		tot=0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				so[++tot]=work(i,j);
			}
		}
		sort(so+1,so+1+tot);
		int q;read(q);
		while(q--){
			ll u;read(u);
			int l=0,r=tot,mid,ans=0;
			while(l<=r){
				mid=(l+r)/2;
				if(so[mid]<=u){
					ans=mid;l=mid+1;
				}else r=mid-1;
			}
			cout<<ans<<endl;
		}
	}
	
	
	return 0;
}