#include <bits/stdc++.h>
using namespace std;
int T,n,m;
struct mat{
	int a[60][60];
	mat(){
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=1e9;
	}
	int* operator [](int b){
		return a[b];
	}
	mat operator *(mat b){
		mat res;
		for(int i=1;i<=n;i++) for(int k=1;k<=n;k++) for(int j=1;j<=n;j++) res[i][j]=min(res[i][j],a[i][k]+b[k][j]);
		return res;
	}
	void out(){
		for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",a[i][j]);
	}
}a[110],b[210];
mat min(mat a,mat b){
	mat res;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) res[i][j]=min(a[i][j],b[i][j]);
	return res;
}
void sol(){
	scanf("%d%d",&n,&m);
	mat G;
	for(int i=1,u,v,w;i<=m;i++) scanf("%d%d%d",&u,&v,&w),G[u][v]=min(G[u][v],w);
	a[1]=mat();
	for(int i=1;i<=n;i++) a[1][i][i]=0;
	b[0]=a[0]=a[1];
	for(int i=1;i<=200;i++) b[i]=b[i-1]*G;
	a[1]=b[100];
	for(int i=2;i<=100;i++) a[i]=a[i-1]*a[1];
	for(int i=199;i>=0;i--) b[i]=min(b[i],b[i+1]);
	int q;
	scanf("%d",&q);
	while(q--){
		int s,t,k,res=1e9;
		scanf("%d%d%d",&s,&t,&k);
		for(int i=1;i<=n;i++) res=min(res,a[k/100][s][i]+b[k%100][i][t]);
		printf("%d\n",res<5e8?res:-1);
	}
}
int main(){
	scanf("%d",&T);
	while(T--) sol();
}