#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 75;
const int INF = 1e9;
int dp[N][N][N], d[N][N];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in3", "r", stdin);
#endif
int n, m;
cin >> n >> m;
vector <array <int, 3>> edges;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
int K, q;
cin >> K >> q;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] = INF;
if (i == j) continue;
for (int k = 0; k <= n; ++k) {
dp[i][j][k] = INF;
}
}
}
for (int i = 0; i < m; ++i) {
auto [u, v, w] = edges[i];
dp[u][v][1] = min(dp[u][v][1], w);
d[u][v] = min(d[u][v], w);
}
// cout << dp[1][2][1] << "\n";
for (int k = 2; k <= min(n, K); ++k) {
for (int z = 1; z <= n; ++z) {
for (int x = 1; x <= n; ++x) {
for (int y = 1; y <= n; ++y) {
dp[x][y][k] = min(dp[x][y][k], dp[x][z][k - 1] + d[z][y]);
}
}
}
}
for (int _q = 1; _q <= q; ++_q) {
int x, y;
cin >> x >> y;
int ans = INF;
for (int k = 1; k <= min(n, K); ++k)
ans = min(ans, dp[x][y][k]);
cout << (ans == INF? -1 : ans) << "\n";
}
return 0;
}
