#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3wByxeT ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
signed main(){
_3wByxeT;
int n,m;
cin>>n>>m;
const int inf=1e10+11;
vec(vi) tbl(n,vi(n,inf));
rep(i,m){
int u,v,w;
cin>>u>>v>>w;
u-=1,v-=1;
tbl[u][v]=min(tbl[u][v],w);
}
auto faf=[&](int v)->vec(vi){
vec(vi) dp(n,vi(n+1,inf));
dp[v][0]=0;
rep(j,n){
rep(i,n){
rep(k,n){
if(tbl[i][k]==inf) continue;
dp[k][j+1]=min(dp[k][j+1],dp[i][j]+tbl[i][k]);
}
}
}
return dp;
};
vec(vec(vi)) qols;
rep(i,n){
qols.pb(faf(i));
}
int k,q;
cin>>k>>q;
k=min(k,n);
rep(i,q){
int v,u;
cin>>v>>u;
v-=1,u-=1;
int res=inf;
rep(j,k+1){
res=min(res,qols[v][u][j]);
}
print((res>=inf?-1:res));
}
//
return 0;
}
