#include <bits/stdc++.h>
using namespace std;
const int N = 75;
int n, m, dp[N][N][N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
dp[i][u][v] = (u != v? 1e9 : 0);
}
}
}
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
dp[1][u][v] = min(dp[1][u][v], c);
}
for (int i = 2; i <= n; ++i) {
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
dp[i][u][v] = dp[i - 1][u][v];
}
}
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
for (int k = 1; k <= n; ++k) {
dp[i][u][v] = min(dp[i][u][v], dp[i - 1][u][k] + dp[1][k][v]);
}
}
}
}
int k, q;
cin >> k >> q;
k = min(k, n);
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
cout << (dp[k][u][v] == 1e9? -1 : dp[k][u][v]) << '\n';
}
return 0;
}
