#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int C = 400;
const int INF = 1e9;

vector<int> Zalgo(const vector<int> &s) {
    vector<int> z(s.size(), s.size());
    for (int i = 1, l = 0, r = 0; i < z[0]; ++i) {
        int j = clamp(r - i, 0, z[i - l]);
        for (; i + j < z[0] and s[i + j] == s[j]; ++j);
        if (i + (z[i] = j) > r) r = i + z[l = i];
    }
    return z;
}

const int D = 50;

pair<int,int> find_cycle(vector<int> v) {
    assert (v.size() == C);
    for (int i = v.size() - 2; i >= 0; i--) {
        v[i] = min(v[i], v[i + 1]);
    }
    v.resize(C - D);
    // for (int k = 0; k < C; k++) {
    //     cerr << v[k] << ' ';
    // }
    // cerr << endl;
    for (int i = v.size() - 1; i >= 1; i--) {
        v[i] -= v[i - 1];
    }
    reverse(v.begin(), v.end());
    const auto Z = Zalgo(v);
    for (int k = 50; k >= 1; k--) {
        if (Z[k] >= k) {
            int s = 0;
            for (int i = 0; i < k; i++)
                s += v[i];
            return { k, s };
        }
    }
    __builtin_unreachable();
}

int g[50][50];
int dp[C][50];
vector<int> seq[50][50];
int cycle[50][50], csum[50][50];

int cdiv(int a, int b) {
    return (a + b - 1) / b;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T; cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = INF;
            }
        }

        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            g[u][v] = min(g[u][v], w);
        }
        
        for (int s = 0; s < n; s++) {
            for (int k = 0; k < C; k++)
                for (int i = 0; i < n; i++)
                    dp[k][i] = INF;
            dp[0][s] = 0;

            for (int k = 0; k + 1 < C; k++)
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        dp[k + 1][j] = min(dp[k + 1][j], dp[k][i] + g[i][j]);

            for (int t = 0; t < n; t++) {
                seq[s][t].clear();
                for (int k = 0; k < C; k++) {
                    seq[s][t].push_back(dp[k][t]);
                }

                tie(cycle[s][t], csum[s][t]) = find_cycle(seq[s][t]);
            }
        }

        int q;
        cin >> q;
        while (q--) {
            int s, t, k;
            cin >> s >> t >> k;
            --s, --t;
            int ans = INF;
            // cerr << "-------\n";
            // for (int i = k; i < C; i++)
            //     cerr << seq[s][t][i] << ' ';
            // cerr << endl;
            // cerr << "-------\n";
            for (int i = k; i < C; i++) {
                ans = min(ans, seq[s][t][i]);
            }
            // cerr << "ans = " << ans << endl;
            for (int i = C - cycle[s][t] - D; i < C - D; i++) if (i < k) {
                int b = cdiv(k - i, cycle[s][t]);
                assert (b >= 1 and
                        i + b * cycle[s][t] >= k and
                        i + (b - 1) * cycle[s][t] < k);
                ans = min(ans, seq[s][t][i] + b * csum[s][t]);
            }
            if (ans == INF)
                cout << -1 << '\n';
            else
                cout << ans << '\n';
        }
    }
    return 0;
}