#include<bits/stdc++.h>
using namespace std;
const int B=100;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<vector<int>> G(n+5,vector<int>(n+5,1e9));
//		for(int i=1;i<=n;i++)G[i][i]=0;
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			G[u][v]=min(G[u][v],w);
		}
		vector<vector<vector<int>>> disS(B+B+5,vector<vector<int>>(n+5,vector<int>(n+5,1e9))),
									disB(B+5,vector<vector<int>>(n+5,vector<int>(n+5,1e9)));
		for(int i=1;i<=n;i++)disS[0][i][i]=0;
		for(int t=1;t<=B+B;t++)
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					for(int k=1;k<=n;k++)
						disS[t][i][k]=min(disS[t][i][k],disS[t-1][i][j]+G[j][k]);
		}
		for(int t=B+B;t>0;t--)
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					disS[t-1][i][j]=min(disS[t-1][i][j],disS[t][i][j]);
		}
		for(int i=1;i<=n;i++)disB[0][i][i]=0;
		for(int t=1;t<=B;t++)
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					for(int k=1;k<=n;k++)
						disB[t][i][k]=min(disB[t][i][k],disB[t-1][i][j]+disS[B][j][k]);
		}
		
//		cerr<<"pre:\n";
//		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cerr<<G[i][j]<<" \n"[j==n];
//		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cerr<<disS[1][i][j]<<" \n"[j==n];
//		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cerr<<disS[2][i][j]<<" \n"[j==n];
		
		
		int q;
		cin>>q;
		while(q--)
		{
			int u,v,x;
			cin>>u>>v>>x;
			int ans=1e9;
			for(int i=1;i<=n;i++)
			{
				ans=min(ans,disS[x%B][u][i]+disB[x/B][i][v]);
//				cerr<<"upd "<<i<<' '<<disS[x%B][u][i]+disB[x/B][i][v]<<endl;
			}
			if(ans==1e9)ans=-1;
			cout<<ans<<"\n";
		}
	}
	
	return 0;
}