#include<cstdio>
#include<cstring>
using namespace std;
const int N=55,INF=0x3f3f3f3f;
int T,n,m,q,s,t,K;
int a[N][N];
int min1(int x,int y){
	return x<y?x:y;
}
int f[N][N][155];
int G[N][N][105];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		memset(a,0x3f,sizeof a);
		for(int i=1,x,y,w;i<=m;i++){
			scanf("%d%d%d",&x,&y,&w);
			a[x][y]=min1(a[x][y],w);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) f[i][j][1]=a[i][j],G[i][j][0]=f[i][j][0]=INF;
			f[i][i][0]=G[i][i][0]=0;
		}
		for(int ii=2;ii<=150;ii++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					int mi=INF;
					for(int k=1;k<=n;k++){
						mi=min1(mi,f[i][k][ii-1]+a[k][j]);
					}
					f[i][j][ii]=mi;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) G[i][j][1]=f[i][j][100];
		}
		for(int ii=2;ii<=100;ii++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					int mi=INF;
					for(int k=1;k<=n;k++){
						mi=min1(mi,G[i][k][ii-1]+G[k][j][1]);
					}
					G[i][j][ii]=mi;
				}
			}
		}
		for(int ii=149;~ii;ii--){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					f[i][j][ii]=min1(f[i][j][ii],f[i][j][ii+1]);
				}
			}
		}
		scanf("%d",&q);
		while(q--){
			scanf("%d%d%d",&s,&t,&K);
			int a=K/100,b=K%100;
			int mi=INF;
			for(int i=1;i<=n;i++){
				mi=min1(mi,G[s][i][a]+f[i][t][b]);
			}
			if(mi==INF) puts("-1");
			else printf("%d\n",mi);
		}
	}
	return 0;
}