#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); i++)
#define revrep(i, a, n) for (auto i = n; i >= (a); i++)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } else return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (auto x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int MatN = 50;
using Vec = array<ll, MatN>;
using Mat = array<Vec, MatN>;
const ll inf = 1ll << 60;

Mat operator *(const Mat &a, const Mat &b) {
	Mat c{};
	rep(i, 0, MatN - 1) rep(j, 0, MatN - 1) c[i][j] = inf;
	rep(i, 0, MatN - 1) rep(k, 0, MatN - 1) rep(j, 0, MatN - 1) chmin(c[i][j], a[i][k] + b[k][j]);
	return c;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		int n, m; cin >> n >> m;
		vector<vector<ll>> d(n, vector<ll>(n, inf));
		rep(i, 0, n - 1) d[i][i] = 0;
		rep(i, 1, m) {
			int x, y, w; cin >> x >> y >> w;
			x--, y--;
			chmin(d[x][y], 1ll * w);
		}
		rep(k, 0, n - 1) rep(i, 0, n - 1) rep(j, 0, n - 1) chmin(d[i][j], d[i][k] + d[k][j]);
		rep(i, 0, n - 1) {
			d[i][i] = inf;
			rep(j, 0, n - 1) if (j != i) chmin(d[i][i], d[i][j] + d[j][i]);
		}

		Mat A{};
		rep(i, 0, MatN - 1) rep(j, 0, MatN - 1) A[i][j] = i == j ? 0 : inf;
		vector<Mat> ss(101, A);
		vector<Mat> bs(101, A);
		rep(i, 0, n - 1) rep(j, 0, n - 1) A[i][j] = d[i][j];
		rep(i, 1, 100) ss[i] = ss[i - 1] * A;
		A = ss[100];
		rep(i, 1, 100) bs[i] = bs[i - 1] * A;
		int q; cin >> q;
		while (q--) {
			int x, y, k; cin >> x >> y >> k;
			x--, y--;
			auto c = bs[k / 100] * ss[k % 100];
			ll ans = c[x][y] < inf ? c[x][y] : -1;
			printf("%lld\n", ans);
		}
	}
	return 0;
}