#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
const int mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline int read () {
	int x = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar ();
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ();
	return x * f;
}
inline void write (int x) {
	if (x < 0) x = -x, putchar ('-');
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}
inline int quickmod (int x, int y) {
	int Ans = 1;
	while (y) {
		if (y & 1) Ans = (1ll * Ans * x) % mod;
		x = (1ll * x * x) % mod;
		y >>= 1;
	}
	return Ans;
}
inline void Add(int &x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}
inline void Dec(int &x, int y) {
	x -= y;
	if(x < 0) x += mod;
}
inline int add(int x, int y) {
	x += y;
	if(x >= mod) x -= mod;
	return x;
}
inline int dec(int x, int y) {
	x -= y;
	if(x < 0) x += mod;
	return x;
}
int n, m, Q;
int w[55][55];
int f[205][55][55], g[205][55][55];
signed main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	int T = read();
	while(T--) {
		n = read(), m = read();
		for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) w[i][j] = inf;
		for(int t = 0; t <= 200; t++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[t][i][j] = g[t][i][j] = inf;
		for(int i = 1; i <= n; i++) f[0][i][i] = g[0][i][i] = 0;
		for(int i = 1; i <= m; i++) {
			int u = read(), v = read(), e = read();
			w[u][v] = min(w[u][v], e);
		}
		for(int t = 1; t <= 200; t++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) f[t][i][j] = min(f[t][i][j], f[t-1][i][k] + w[k][j]);
		for(int t = 1; t <= 200; t++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) g[t][i][j] = min(g[t][i][j], g[t-1][i][k] + f[200][k][j]);
		for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int t = 199; t >= 0; t--) f[t][i][j] = min(f[t+1][i][j], f[t][i][j]), g[t][i][j] = min(g[t+1][i][j], g[t][i][j]);
		Q = read();
		while(Q--) {
			int x = read(), y = read(), lim = read();
			int Ans = inf;
			for(int i = 1; i <= n; i++) Ans = min(Ans, g[lim/200][x][i] + f[lim%200][i][y]);
			for(int i = 1; i <= n; i++) Ans = min(Ans, g[lim/200 + 1][x][i] + f[0][i][y]);
//			Ans = min(Ans, g[lim/200+1][x][y]);
			if(Ans == inf) puts("-1");
			else write(Ans), putchar('\n');
		}
	}
	return 0;
}
/*
*/