#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e14;
int n;
vector <vector <int>> iden;
vector <vector <int>> mul (vector <vector <int>> a, vector <vector <int>> b) {
vector <vector <int>> ret (n + 1, vector <int> (n + 1));
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) ret[i][j] = inf;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
ret[i][j] = min(ret[i][j], a[i][k] + b[k][j]);
}
}
}
return ret;
}
vector <vector <int>> power (vector <vector <int>> a, int b) {
if (b == 1) return a;
auto u = power(a, b >> 1);
u = mul(u, u);
if (b & 1) u = mul(u, a);
return u;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n; int m;
cin >> m;
vector <vector <int>> adj(n + 1, vector <int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
adj[i][j] = inf;
}
}
}
while (m--) {
int a, b, c;
cin >> a >> b >> c;
adj[a][b] = min(adj[a][b], c);
}
iden = vector <vector <int>> (n + 1, vector <int> (n + 1));
for (int i = 1; i <= n; i++) iden[i][i] = 1;
int k, q;
cin >> k >> q;
adj = power(adj, k);
while (q--) {
int a, b;
cin >> a >> b;
cout << (adj[a][b] >= inf ? -1 : adj[a][b]) << '\n';
}
}
