// #ifdef __AVX2__ // #pragma GCC target "avx2" // #endif // #pragma GCC optimize "O3" // #pragma GCC optimize "unroll-loops" #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; #define int long long #define elif else if #define all(l) begin(l),end(l) #define rall(l) rbegin(l),rend(l) #define append push_back #define print(l) for(auto i:l) cout<<i<<' '; cout<<endl; #define pprint(a,b) cout<<a<<' '<<b<<endl; #define inp(l) for(auto &i:l) cin>>i; // #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define pai make_pair #define endl "\n" #define pii pair<int,int> #define fi first #define se second #define vec vector #define ins(a,b,c) a.insert(begin(a)+b,c); // const int mod=998244353; const int mod1=998244353; const int mod=1e9+7; const int N=75; vec<pii>G[N]; int dis[N][N][N]; int n,m; struct sta{ int d,st,en,ed; }; struct com{ bool operator()(const sta& st1, const sta& st2){ return st1.d>st2.d; } }; void comp(){ priority_queue<sta,vec<sta>,com>q; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=0;k<=n;k++) dis[i][j][k]=1e18; } dis[i][i][0]=0; sta st; st.d=st.ed=0; st.st=st.en=i; q.push(st); } while(q.size()){ sta a=q.top(); int di=a.d,st=a.st,en=a.en,ed=a.ed; q.pop(); if(dis[st][en][ed]!=di) continue; if(ed+1>n) continue; for(auto [v,w]:G[en]){ if(dis[st][v][ed+1]>di+w){ dis[st][v][ed+1]=di+w; sta st1; st1.d=di+w; st1.st=st; st1.en=v; st1.ed=ed+1; q.push(st1); } } } } int iter=1,itera=1; void solve(){ cin>>n>>m; vec<vec<int>>ad(n+1,vec<int>(n+1,1e10)); for(int i=0;i<m;i++){ int a,b,t; cin>>a>>b>>t; ad[a][b]=min(ad[a][b],t); } for(int a=1;a<=n;a++){ for(int b=1;b<=n;b++){ if(ad[a][b]<=1e9) G[a].append({b,ad[a][b]}); } } comp(); // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // for(int k=0;k<=n;k++){ // cout<<i<<' '<<j<<' '<<k<<' '<<dis[i][j][k]<<endl; // } // } // } int k,q; cin>>k>>q; for(int i=0;i<q;i++){ int a,b; cin>>a>>b; int ans=1e18; for(int j=0;j<=min(n,k);j++) ans=min(ans,dis[a][b][j]); if(ans>1e9*n) cout<<"-1\n"; else cout<<ans<<endl; } } signed main(){ // freopen("","r",stdin); // freopen("","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<<fixed<<setprecision(20); // cin>>itera; for(iter=1;iter<=itera;iter++) solve(); }