#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int inf = 1e9;
const int mxn = 5e4+5;

int n,m,q;
vector<array<int,2>> adj[mxn];
vector<array<int,2>> hull[mxn];

void make_hull(vector<array<int,2>> &a) {
	sort(all(a));
	vector<array<int,2>> hull;
	for (auto pt : a) {		
		if (sz(hull) && hull.back()[0] == pt[0]) continue;

		if (sz(hull) < 2) {
			hull.push_back(pt);
			continue;
		}
		int yy = hull.back()[1];
		if (pt[1] >= yy) continue;
		
		while (sz(hull) >= 2) {
			auto [x1,y1] = hull[sz(hull)-2];
			auto [x2,y2] = hull[sz(hull)-1];
			auto [x3,y3] = pt;
			if (x2*(y3-y1) <= (y2-y1)*(x3-x1)) {
				hull.pop_back();
			} else {
				break;
			}
		}
		hull.push_back(pt);
	}
	swap(a,hull);
	hull.clear();
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m;
	for (int i=0; i<m; i++) {
		int u,v,c; cin>>u>>v>>c;
		adj[u-1].push_back({v-1,c});
	}
	hull[0].push_back({0,0});
	for (int i=0; i<n; i++) {
		for (auto [v,t] : adj[i]) {
			if (t) {
				for (auto [x,y] : hull[i]) {
					hull[v].push_back({x,y+1});
				}
			} else {
				for (auto [x,y] : hull[i]) {
					hull[v].push_back({x+1,y});
				}
			}
			make_hull(hull[v]);
		}
	}
	cin>>q;
	while (q--) {
		int a,b,v; cin>>a>>b>>v; --v;
		int mv = inf;
		for (auto [x,y] : hull[v]) {
			mv = min(mv,x*a+y*b);
		}
		cout<<mv<<"\n";
	}
	
}