// Lets goto the next level
// AIM 6* at CC and CM at CF *__*
// Striver_79
#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define mod (int)1000000007
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define int long long
#define ll long long
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define in(x) scanf("%intd", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define fi first
#define se second
#define kitna se
#define endl "\n"
#define pi pair<int, int>
#define LL long long
const int MAXN = (int)((1e5) + 10);
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;}
bool isPrime(int N){ for(int i=2;i*i<=N;++i){if(N%i==0) return false;}return true;}
int cbrt(int x){ int lo=1,hi=min(2000000ll,x);while(hi-lo>1){int mid=(lo+hi)/2;if(mid*mid*mid<x){lo=mid;}else hi=mid;}if(hi*hi*hi<=x) return hi;else return lo;}
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int nax = (int)(2*1e5+10);
//vector<int>vec[nax];
// const int N = 5;
// int SPF[N+5];
// void SOF()
// {
// SPF[1] = 1;
// for (int i=2; i<N; i++)
// SPF[i] = i;
// for (int i=4; i<N; i+=2)
// SPF[i] = 2;
// for (int i=3; i*i<N; i++)
// {
// if (SPF[i] == i)
// {
// for (int kon=i*i; kon<N; kon+=i)
// if (SPF[kon]==kon)
// SPF[kon] = i;
// }
// }
// }
// int C[1005][1005];
// int binomialCoeff(int n, int k)
// {
// // int C[n + 1][k + 1];
// int i, j;
// // Caculate value of Binomial Coefficient
// // in bottom up manner
// for (i = 0; i <= n; i++)
// {
// for (j = 0; j <= min(i, k); j++)
// {
// // Base Cases
// if (j == 0 || j == i)
// C[i][j] = 1;
// // Calculate value using previosly
// // stored values
// else
// C[i][j] = C[i - 1][j - 1] +
// C[i - 1][j];
// }
// }
// return C[n][k];
// }
bool isPowerOfTwo(int x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x&(x-1)));
}
vector<pi>vec[3010],rev[3010], kitna[3010];
int n,m,q;
int dist[3010];
bool vis[3010];
void dfs(int node)
{
int c = dist[node];
vis[node] = true;
for(auto it:rev[node])
{
if(!vis[it.fi]) dfs(it.fi);
c += dist[it.fi];
for(auto iter:kitna[it.first])
{
int raj1 = iter.first+it.se;
int raj2 = iter.se+1;
kitna[node].pb(raj1,raj2);
}
}
dist[node] = c;
}
// Taken from https://codeforces.com/blog/entry/51275?locale=en
const long long Q = -(1ll << 60);
struct line {
long long m, p;
mutable set<line>::iterator prev;
};
set<line>::iterator null;
bool operator<(const line& a, const line& b)
{
if (b.p != Q && a.p != Q) {
return a.m < b.m;
}
if (b.p == Q) {
if (a.prev == null)
return true;
bool ok = true;
if ((a.prev->m - a.m) < 0)
ok = !ok;
if (ok) {
return (a.p - a.prev->p) < (a.prev->m - a.m) * b.m;
}
else {
return (a.p - a.prev->p) > (a.prev->m - a.m) * b.m;
}
}
else {
if (b.prev == null)
return false;
bool ok = true;
if ((b.prev->m - b.m) < 0)
ok = !ok;
if (ok) {
return !((b.p - b.prev->p) < a.m * (b.prev->m - b.m));
}
else {
return !((b.p - b.prev->p) > a.m * (b.prev->m - b.m));
}
}
}
class convex_hull {
public:
set<line> convex;
set<line>::iterator next(set<line>::iterator ii)
{
set<line>::iterator gg = ii;
gg++;
return gg;
}
set<line>::iterator prev(set<line>::iterator ii)
{
set<line>::iterator gg = ii;
gg--;
return gg;
}
bool bad(set<line>::iterator jj)
{
set<line>::iterator ii, kk;
if (jj == convex.begin())
return false;
kk = next(jj);
if (kk == convex.end())
return false;
ii = prev(jj);
line a = *ii, c = *kk, b = *jj;
bool ok = true;
if ((b.m - a.m) < 0)
ok = !ok;
if ((b.m - c.m) < 0)
ok = !ok;
if (ok) {
return (c.p - b.p) * (b.m - a.m) <= (a.p - b.p) * (b.m - c.m);
}
else {
return (c.p - b.p) * (b.m - a.m) >= (a.p - b.p) * (b.m - c.m);
}
}
void del(set<line>::iterator ii)
{
set<line>::iterator jj = next(ii);
if (jj != convex.end()) {
jj->prev = ii->prev;
}
convex.erase(ii);
}
void add(long long m, long long p)
{
null = convex.end();
line g;
g.m = m;
g.p = p;
set<line>::iterator ii = convex.find(g);
if (ii != convex.end()) {
if (ii->p >= p)
return;
del(ii);
}
convex.insert(g);
ii = convex.find(g);
set<line>::iterator jj = next(ii);
if (jj != convex.end())
jj->prev = ii;
if (ii != convex.begin()) {
ii->prev = prev(ii);
}
else {
ii->prev = convex.end();
}
if (bad(ii)) {
del(ii);
return;
}
jj = next(ii);
while (jj != convex.end() && bad(jj)) {
del(jj);
jj = next(ii);
}
if (ii != convex.begin()) {
jj = prev(ii);
while (ii != convex.begin() && bad(jj)) {
del(jj);
jj = prev(ii);
}
}
}
long long query(long long x)
{
null = convex.end();
line y;
y.m = x;
y.p = Q;
set<line>::iterator ii = convex.lower_bound(y);
ii--;
return ii->m * x + ii->p;
}
};
convex_hull gg[3010];
signed main(){
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
// freopen("output.txt", "w", stdout);
#endif
fio;
int t = 1;
// cin >> t;
dist[1] = 1;
kitna[1].pb(0,0);
while(t--)
{
cin >> n >> m;
for0(i,m)
{
int x,y,c;
cin >> x >> y >> c;
rev[y].pb(x,c);
vec[x].pb(y,c);
}
vector<pi>qq;
int q;
cin>> q;
while(q--)
{
int x,y;
cin >> x >> y;
qq.pb(x,y);
}
for1(i,n)
{
if(!vis[i]) dfs(i);
}
gg[1]
for(int i = 2;i<=n;i++)
{
for(auto it:kitna[i])
gg[i].add(-it.se,-it.fi);
}
int gin = 0;
for(auto it:qq)
{
if(it.fi==2)
{
if(kitna[it.se].size()==0)
{
cout << "No Path Exists\n";
}
else if(it.se!=1)
cout << -1*gg[it.se].query(gin) << endl;
else
cout << 0 << endl;
}
else
{
gin += it.se;
}
}
}
rr;
}