#include <bits/stdc++.h>
#define pii pair <int , int>
#define pll pair <LL , LL>
#define mp make_pair
#define fs first
#define sc second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

//const int Mxdt=100000;
//static char buf[Mxdt],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;

template <typename T>
void read(T &x) {
	T f=1;x=0;char s=getchar();
	while(s<'0'||s>'9') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s^'0');s=getchar();}
	x *= f;
}

template <typename T>
void write(T x , char s='\n') {
	if(!x) {putchar('0');putchar(s);return;}
	if(x<0) {putchar('-');x=-x;}
	T t = 0 , tmp[25] = {};
	while(x) tmp[t ++] = x % 10 , x /= 10;
	while(t -- > 0) putchar(tmp[t] + '0');
	putchar(s);
}

const LL inf = 1e18;

LL dis1[105][55][55] , dis2[105][55][55] , dis[55][55];
int n , m;

int main() {
	int T;read(T);
	while(T -- > 0) {
		for (int i = 0; i <= 100; ++i) for (int j = 0; j <= 50; ++j) for (int k = 0; k <= 50; ++k) {
			dis1[i][j][k] = dis2[i][j][k] = inf;
			dis[j][k] = inf;
			if(j == k && !i) dis1[i][j][k] = dis2[i][j][k] = dis[j][k] = 0;
			if(j == k) dis[j][k] = 0;
		}
		read(n),read(m);
		for (int i = 1; i <= m; ++i) {
			int u , v;LL w;
			read(u),read(v),read(w);
			dis1[1][u][v] = min(dis1[1][u][v] , w); 
			dis[u][v] = min(dis[u][v] , w);
		}
		for (int u = 1; u <= n; ++u) for (int k = 1; k <= n; ++k) for (int v = 1; v <= n; ++v) {
			dis[u][v] = min(dis[u][v] , dis[u][k] + dis[k][v]);
		}
		for (int i = 2; i <= 100; ++i) {
			for (int u = 1; u <= n; ++u) for (int k = 1; k <= n; ++k) for (int v = 1; v <= n; ++v) {
				dis1[i][u][v] = min(dis1[i][u][v] , dis1[i - 1][u][k] + dis1[1][k][v]);
			}
		}
		for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) dis2[1][u][v] = dis1[100][u][v];
		for (int i = 2; i <= 100; ++i) {
			for (int u = 1; u <= n; ++u) for (int k = 1; k <= n; ++k) for (int v = 1; v <= n; ++v) {
				dis2[i][u][v] = min(dis2[i][u][v] , dis2[i - 1][u][k] + dis2[1][k][v]);
			}
		}
		int Q;read(Q);
		while(Q -- > 0) {
			int s , t , k;
			read(s),read(t),read(k);
			int p = k / 100 , q = k % 100;
			LL ans = inf;
			for (int w = 1; w <= n; ++w) for (int d = 1; d <= n; ++d) ans = min(ans , dis1[q][s][w] + dis2[p][w][d] + dis[d][t]);
			if(ans != inf) write(ans);
			else puts("-1");
		} 
	}
	return 0;
}