// #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();
}
