#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 71;
vector <pair<int, int> > adj[N];
vector <vector<vector<int> > > ans(N);
int32_t main(){
fast
int n, m;
cin >> n >> m;
vector <vector<int> > temp(n+1, vector<int>(n + 1, inf));
for(int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
temp[a][b] = min(temp[a][b], w);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) temp[i][j] = 0;
if(temp[i][j] == inf) continue;
adj[i].push_back({j, temp[i][j]});
}
}
int K, Q;
cin >> K >> Q;
K = min(K, n - 1);
auto dijkstra = [&](int st) {
// cout << st << ":\n";
vector <vector<int> > dist(N, vector<int>(N, inf));
vector <vector<bool> > vis(N, vector<bool>(N));
dist[st][0] = 0;
priority_queue <array<int, 3>, vector<array<int,3> >, greater<array<int, 3>> > pq; // {k, -v, node}
pq.push({0, 0, st});
while(!pq.empty()) {
auto [k, v, node] = pq.top();
pq.pop();
if(k > K or vis[node][k]) continue;
// cout << node << " " << k << " " << v << "\n";
dist[node][k] = v;
vis[node][k] = 1;
for(auto [to, w]:adj[node]) {
if(dist[to][k + 1] == inf) {
pq.push({k + 1, v + w, to});
}
}
}
ans[st] = dist;
};
for(int i = 1; i <= n; i++) {
dijkstra(i);
}
while(Q--) {
int a, b;
cin >> a >> b;
cout << (ans[a][b][K] == inf ? -1 : ans[a][b][K]) << "\n";
}
}
