#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int64_t INFL = 1e18L;
void minSelf(int &x, int y) {
if (y < x) {
x = y;
}
}
void testCase() {
int n, m;
cin >> n >> m;
vector<vector<int>> wt(n + 1, vector<int>(n + 1, INF));
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
minSelf(wt[u][v], w);
}
vector<vector<pair<int, int>>> g(n + 1);
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
if (u != v && wt[u][v] != INF) {
g[u].emplace_back(v, wt[u][v]);
}
}
}
int k, q;
cin >> k >> q;
minSelf(k, n);
vector<vector<int64_t>> best(n + 1, vector<int64_t>(n + 1, INFL));
for (int s = 1; s <= n; ++s) {
vector<vector<int64_t>> dp(n + 1, vector<int64_t>(k + 1, INFL)); /// costul minim sa ajung de la s la nod cu lungime len
vector<vector<bool>> inQ(n + 1, vector<bool>(k + 1));
dp[s][0] = 0;
queue<pair<int, int>> q;
q.emplace(s, 0);
inQ[s][0] = true;
while (!q.empty()) {
int u, len;
tie(u, len) = q.front();
q.pop();
inQ[u][len] = false;
for (auto it : g[u]) {
int v, w;
tie(v, w) = it;
if (dp[v][len + 1] > dp[u][len] + w) {
dp[v][len + 1] = dp[u][len] + w;
if (len + 1 < k && !inQ[v][len + 1]) {
q.emplace(v, len + 1);
inQ[v][len + 1] = true;
}
}
}
}
for (int t = 1; t <= n; ++t) {
best[s][t] = *min_element(dp[t].begin(), dp[t].end());
}
}
for (int i = 0; i < q; ++i) {
int s, t;
cin >> s >> t;
if (best[s][t] == INFL) {
cout << "-1\n";
} else {
cout << best[s][t] << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
