#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=71;
ll adj[maxn][maxn];
ll dis[maxn][maxn];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i=0;i<maxn;i++){
for (int j=0;j<maxn;j++){
adj[i][j]=inf;
}
adj[i][i]=0;
}
ll n,e,a,b,w;
cin>>n>>e;
for (int i=0;i<e;i++){
cin>>a>>b>>w;
adj[a][b]=min(adj[a][b],w);
}
ll k,y,u,x;
cin>>k>>y;
queue<ii> q;
for (int i=0;i<y;i++){
cin>>a>>b;
memset(dis,-1,sizeof(dis));
q.emplace(a,0);
dis[a][0]=0;
while (q.size()){
u=q.front().first;
x=q.front().second;
q.pop();
if (x>k) continue;
for (int i=1;i<=n;i++){
if (dis[i][x+1]!=-1){
dis[i][x+1]=min(dis[i][x+1],dis[u][x]+adj[u][i]);
} else{
dis[i][x+1]=dis[u][x]+adj[u][i];
q.emplace(i,x+1);
}
}
}
ll ans=inf;
for (int i=0;i<=k;i++){
if (dis[b][i]!=-1) ans=min(ans,dis[b][i]);
}
cout<<(ans==inf?-1:ans)<<endl;
}
return 0;
}
