#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<bool> vb;
#define fi first
#define se second
#define pb push_back
#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define sp <<" "<<
#define DEBUG(x) cout<<(#x) sp x<<endl
const int INF=1e18;
const int MAXN=75;
int n,m,k,q;
vii adj[MAXN];
int d[MAXN][MAXN];
int tut[MAXN][MAXN];
void dij(int bas){
set<pair<int,pii>> s;
s.insert({0,{0,bas}});
FORE(i,1,n+1) d[bas][i]=INF;
d[bas][bas]=0;
while(!s.empty()){
auto el=*s.begin();
s.erase(el);
int nd=el.se.se;
int kk=el.se.fi;
if(kk>=k) continue;
for(auto [kom,cost]:adj[nd]){
if(d[bas][kom]>d[bas][nd]+cost){
if(d[bas][kom]!=INF) s.erase({d[bas][kom],{tut[bas][kom],kom}});
d[bas][kom]=d[bas][nd]+cost;
tut[bas][kom]=kk+1;
s.insert({d[bas][kom],{tut[bas][kom],kom}});
}
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
map<pii,int> edg;
cin>>n>>m;
FOR(i,m){
int a,b,c;
cin>>a>>b>>c;
if(edg[{a,b}]==0) edg[{a,b}]=c;
else edg[{a,b}]=min(edg[{a,b}],c);
}
for(auto el:edg){
int a=el.fi.fi;
int b=el.fi.se;
int c=el.se;
adj[a].pb({b,c});
}
cin>>k>>q;
FORE(i,1,n+1){
dij(i);
}
while(q--){
int a,b;
cin>>a>>b;
cout<<(d[a][b]!=INF?d[a][b]:-1)<<endl;
}
}
