// 01001100 01001111 01010100 01000001 \\ // \\ // ╦ ╔═╗╔╦╗╔═╗ \\ // ║ ║ ║ ║ ╠═╣ \\ // ╩═╝╚═╝ ╩ ╩ ╩ \\ // \\ // 01001100 01001111 01010100 01000001 \\ #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define ld long double #define terminator main #define pll pair<ll,ll> #define add insert #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) const int N = 71; int n; int x[N][N]; int dp[N][N][N]; vector<pii> a[N]; void compute(int s){ int v, k, w; for(int i = 1; i <= n; i++) for(int j = 0; j < n; j++) dp[s][i][j] = 1e9; dp[s][s][0] = 0; for(int i = 1; i <= n; i++) dp[s][i][n] = 0; priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> Q; Q.push({0, {0, s}}); while(!Q.empty()){ w = Q.top().ff; v = Q.top().ss.ss; k = Q.top().ss.ff; Q.pop(); if(w == dp[s][v][k]){ for(auto & [i, j] : a[v]){ if(w + j < dp[s][i][k + 1]){ dp[s][i][k + 1] = w + j; Q.push({w + j, {k + 1, i}}); } } } } } void solve(){ int m, v, u, w, k, q, ans; cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) x[i][j] = 1e9; for(int i = 1; i <= m; i++){ cin >> v >> u >> w; x[v][u] = min(x[v][u], w); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(x[i][j] < 1e9) a[i].append({j, x[i][j]}); for(int i = 1; i <= n; i++) compute(i); cin >> k >> q; k = min(k, n - 1); while(q--){ cin >> v >> u; ans = 1e9; for(int i = 0; i <= k; i++) ans = min(ans, dp[v][u][i]); if(ans < 1e9) cout << ans << nl; else cout << "-1\n"; } } int terminator(){ L0TA; int T = 1; //cin >> T; while(T--) solve(); return 0; }