#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 75, INF = 0x3f3f3f3f3f3f3f3f;
// pair<int, int> dist[N][N];
int dist[N][N];
vector<pair<int, int>> adj[N];
pair<int, int> operator+(pair<int, int> a, pair<int, int> b){
return {a.first+b.first, a.second+b.second};
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
while(m--){
int u, v, t;
cin >> u >> v >> t;
adj[u].push_back({v, t});
// dist[u][v] = min(dist[u][v], {t, 1});
}
int k, q;
cin >> k >> q;
// for(int l = 1; l <= n; ++l){
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= n; ++j){
// pair<int, int> t = dist[i][l]+dist[l][j];
// if(t.second > k || t.first >= 1e9) continue;
// dist[i][j] = min(dist[i][j], t);
// }
// }
// }
while(q--){
int x, y;
cin >> x >> y;
// if(dist[x][y].second > k || dist[x][y].first >= 1e9) cout << -1 << '\n';
// else cout << dist[x][y].first << '\n';
memset(dist, 0x3f, sizeof dist);
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({dist[x][0] = 0, x, 0});
while(!pq.empty()){
auto [d, u, c] = pq.top(); pq.pop();
if(dist[u][c] < d) continue;
for(auto [v, w] : adj[u]){
if(c+1 <= k && dist[v][c+1] > d+w){
pq.push({dist[v][c+1] = d+w, v, c+1});
}
}
}
int mn = INF;
for(int i = 0; i <= min(n, k); ++i) mn = min(mn, dist[y][i]);
cout << mn << '\n';
}
}
