#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int maxn = 75;
const int oo = 1e9 + 7;
const ll inf = 1e18;
using pii = pair<int, int>;
using piii = pair<int, pair<int, int>>; // {distance, {vertex, road}}
int n, m, k, q, line = 0;
vector<pii> adj[maxn];
int mat[maxn][maxn];
int dis[maxn][maxn][maxn*maxn];
priority_queue<piii, vector<piii>, greater<piii>> pq;
void dijkstra(int u) {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= line; j++)
dis[u][i][j] = oo;
}
dis[u][u][0] = 0;
pq.push({0, {u, 0}});
while (!pq.empty()) {
piii t = pq.top();
int ver = t.second.first;
int road = t.second.second;
int d = t.first;
pq.pop();
if (dis[u][ver][road] != d)
continue;
for (auto [v, j] : adj[ver]) {
if (dis[u][v][road + 1] > dis[u][ver][road] + j) {
dis[u][v][road + 1] = dis[u][ver][road] + j;
pq.push({dis[u][v][road + 1], {v, road + 1}});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
mat[i][j] = oo;
}
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
mat[u][v] = min(mat[u][v], c);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (mat[i][j] != oo) {
adj[i].push_back({j, mat[i][j]});
// adj[j].push_back({i, mat[i][j]});
line++;
}
}
}
cin >> k >> q;
for (int i = 1; i <= n; i++) {
dijkstra(i);
}
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
int res = oo;
for (int j = 0; j <= min(k, line); j++)
res = min(res, dis[a][b][j]);
if (res == oo)
cout << -1 << '\n';
else
cout << res << '\n';
}
}
