// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <unordered_map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> using namespace std; #define int long long #define endl "\n" #define fi first #define se second const int M=1e9+7; const int inf = 1e14; const int LOG=18; const int N=7e1+5; int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r; int dp[N][N][N]; int ans[N][N]; vector<pair<int,int>>a[N]; void solve(){ cin >> n >> m; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ ans[i][j]=inf; if (i==j)ans[i][j]=0; for (int k=0;k<=n;k++){ dp[i][j][k]=inf; if (i==j)dp[i][j][k]=0; } } } for (int i=0;i<m;i++){ cin >> x >> y >> z; if (dp[x][y][1]<z)continue; dp[x][y][1]=z; } for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ if (!dp[i][j][1] or dp[i][j][1]==inf)continue; a[i].push_back({j,dp[i][j][1]}); // ans[i][j]=dp[i][j][1]; } } for (int k=0;k<=n-1;k++){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ for (auto [l,w]:a[j]){ dp[i][l][k+1]=ans[i][l]; dp[i][l][k+1]=min(dp[i][l][k+1],dp[i][j][k]+w); ans[i][l]=min(ans[i][l],dp[i][l][k+1]); } } } } cin >> k >> q; k=min(k,n); for (int i=0;i<q;i++){ cin >> x >> y; if (dp[x][y][k]==inf){ cout << -1 << endl; continue; } cout << dp[x][y][k] << endl; } } signed main() { // ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE // cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE cout << fixed << setprecision(9); srand(time(0)); // int t=1; // cin >> t; for (int _=1;_<=t;_++){ solve(); q++; } }