// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;
void fast_io(){
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
cout << setprecision(9);
}
#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
const int N = 75;
int dp[N][N][N], adj[N][N];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
adj[i][j] = 1e18;
for (int k = 0; k <= n; k++){
dp[i][j][k] = 1e18;
}
}
}
int m; cin >> m;
for (int i = 1; i <= m; i++){
int u, v, t; cin >> u >> v >> t;
adj[u][v] = min(t, adj[u][v]);
}
int k, q; cin >> k >> q;
k = min(n, k);
for (int st = 1; st <= n; st++){
dp[st][st][0] = 0;
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;
q.push({0, 0, st});
while (q.size()){
int dist = q.top()[0], len = q.top()[1], u = q.top()[2];
q.pop();
if (len == k) continue;
for (int v = 1; v <= n; v++){
if (dp[st][v][len + 1] > dist + adj[u][v]){
dp[st][v][len + 1] = dist + adj[u][v];
q.push({dp[st][v][len + 1], len + 1, v});
}
}
}
}
for (int i = 1; i <= q; i++){
int u, v; cin >> u >> v;
int ans = 1e18;
for (int j = 0; j <= k; j++) ans = min(ans, dp[u][v][j]);
if (ans == 1e18) cout << -1 << endl;
else
cout << ans << endl;
}
return;
}
signed main() {
fast_io();
srand(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
