#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, q, ans[50050];
vector<array<int, 2>> v[50050], c[50050];
vector<array<int, 3>> Q[50050];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a, b, c; cin >> a >> b >> c;
        v[b].push_back({a, c});
    }
    cin >> q;
    for(int i=1;i<=q;i++) {
        int a, b, c; cin >> a >> b >> c;
        Q[c].push_back({a, b, i});
    }

    c[1].push_back({0, 0});
    for(int i=1;i<=n;i++) {
        c[i].push_back({n, n});
        for(auto [x, y] : v[i]) {
            vector<array<int, 2>> C;

            int j = 0, k = 0;
            while(j < c[i].size() || k < c[x].size()) {
                if(k == c[x].size() || (j < c[i].size() && c[i][j][0] >= c[x][k][0]+!y)) {
                    auto [X, Y] = c[i][j++];
                    C.push_back({X, Y});
                } else {
                    auto [X, Y] = c[x][k++];
                    (y ? Y : X) += 1;
                    C.push_back({X, Y});
                }
            }

            c[i] = C;
        }

        for(auto [a, b, id] : Q[i]) {
            ans[id] = INT_MAX;
            for(auto [x, y] : c[i]) ans[id] = min(ans[id], a*x + b*y);
        }

        if(i > 1000) c[i-1000].clear();
    }

    for(int i=1;i<=q;i++) cout << ans[i] << "\n";
}