#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()) {
                int X = 0, Y = 0;
                if(k == c[x].size() || (j < c[i].size() && (c[i][j][0] > c[x][k][0]+!y || (c[i][j][0] == c[x][k][0]+!y && c[i][j][1] < c[x][k][1]+y)))) {
                    X = c[i][j][0], Y = c[i][j][1], j++;
                } else {
                    X = c[x][k][0]+!y, Y = c[x][k][1]+y, k++;
                }
                while(!C.empty() && C.back()[1] >= Y) C.pop_back();
                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";
}