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

const int N = 5e4+10;
int n,m,q;
vector<int> A[N], B[N];
struct node{
    int x,y;
    bool operator < (const node &a)const{
        return x!=a.x?x<a.x:y<a.y;
    }
};
vector<node>p[N], tmp;

void merge(vector<node> &A, const vector<node> &B){
   int i=0, j=0, ta=A.size(), tb=B.size();
   tmp.clear();
   while (i<ta&&j<tb) tmp.push_back(A[i]<B[j]?A[i++]:B[j++]);
   while (i<ta) tmp.push_back(A[i++]);
   while (j<tb) tmp.push_back(B[j++]);
   A.clear();
   for (node x:tmp){
      if (A.empty()) A.push_back(x);
      else if (x.y < A.back().y) {
        for (;A.size()>1;A.pop_back()) {
            node a=A[A.size()-2], b = A.back();
            if ((a.y - b.y) * (b.x - x.x) < (b.y - x.y) * (a.x - b.x))
              break;
        }
        A.push_back(x); 
      }
   }
   return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i=1;i<=m;++i){
        int u,v,c;
        cin >> u >> v >> c;
        if (u==v) cout <<"Failed\n";
        if (!c) A[u].push_back(v);
          else B[u].push_back(v);
    }
    p[1].push_back({0,0});
    for (int u=1;u<=n;++u) {
        vector<node> temp = p[u];
        for (auto &x:temp)x.x++;
        for (int v:A[u]) merge(p[v], temp);
        for (auto &x:temp)x.x--, x.y++;
        for (int v:B[u]) merge(p[v], temp);
    }

    cin >> q;
    for (int i=1;i<=q;++i){
        int a,b,u,ans=1e9;
        cin >>a>>b>>u;
        for (node x:p[u])
          ans = min(ans, a*x.x+b*x.y);
        cout <<ans<<endl;
    }
    return 0;
}