// #include <bits/stdc++.h> #include <iostream> #include <vector> #include <queue> using namespace std; #define endl "\n" #define pb push_back // #define int long long #define fi first #define se second const int N = 74, M = 1e9 + 7, LG = 20; int n , A[N] , m , dis[N][N][N] , q , k , u , v , w , wi[N][N]; vector<pair<int,int>> lis[N]; void solve(){ for (int i=0 ; i<N ; i++){ for (int j=0 ; j<N ; j++){ for (int k=0 ; k<N ; k++){ dis[i][j][k] = 1e9; if (i==j){ dis[i][j][k] = 0; } } } } cin >> n >> m; for (int i=1 ; i<=m ; i++){ cin >> u >> v >> w; if (wi[u][v] == 0){ wi[u][v] = w; continue; } wi[u][v] = min(wi[u][v] , w); } for (int i=1 ; i<=n ; i++){ for (int j=1 ; j<=n ; j++){ if (!wi[i][j]) continue; lis[i].pb({j , wi[i][j]}); dis[i][j][1] = wi[i][j]; } } for (int k=2 ; k<=n ; k++){ for (int i=1 ; i<=n ; i++){ for (int j=1 ; j<=n ; j++){ dis[i][j][k] = dis[i][j][k-1]; for (int l=1 ; l<=n ; l++){ for (int t=1 ; t<k ; t++){ dis[i][j][k] = min(dis[i][j][k] , dis[i][l][t] + dis[l][j][k-t]); } } } } } cin >> k >> q; k = min(k , n); while(q--){ cin >> u >> v; int ans = 1e9; for (int i=0 ; i<=k ; i++){ ans = min(ans , dis[u][v][i]); } if (ans == 1e9) ans = -1; cout << ans << endl; } } signed main(){ // freopen("" , "r" , stdin); // freopen("" , "w" , stdout); // cout << setprecision(30); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ts = 1; // cin >> ts; while(ts--){ solve(); } }