#include <bits/stdc++.h> #define int long long using namespace std; const long long N = 76; int dp[N][N][N]; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) dp[i][j][k] = 1e18; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][i][j] = 0; } } int u, v, d; for (int i = 0; i < m; i++) { cin >> u >> v >> d; dp[u][v][1] = d; } int k, q; cin >> k >> q; k = min(k, 73LL); for (int i = 2; i <= k; i++) { for (int mid = 1; mid <= n; mid++) { for (int u = 1; u <= n; u++) { for (int v = 1; v <= n; v++) { dp[u][v][i] = min(dp[u][v][i], dp[u][v][i - 1]); dp[u][v][i] = min(dp[u][v][i], dp[u][mid][i - 1] + dp[mid][v][1]); } } } } // cout << dp[1][4][2] << endl; for (int i = 0; i < q; i++) { cin >> u >> v; if (dp[u][v][k] == 1e18) { cout << -1 << endl; } else cout << dp[u][v][k] << endl; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { // cout << "Case #" << i << ':' << ' '; solve(); cout << endl; } return 0; }