// #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; }