#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 70;
int dis[N + 1][N + 1],res[N + 1][N + 1][N + 1];
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
if(i == j) continue;
dis[i][j] = INT_MAX;
}
}
for(int i = 0;i < m;i++) {
int a,b,t;
cin>>a>>b>>t;
dis[a][b] = min(dis[a][b],t);
}
for(int i = 0;i <= n;i++) {
for(int j =0;j <= n;j++) {
for(int t = 0;t <= n;t++) {
res[i][j][t] = INT_MAX;
}
}
}
for(int i = 1;i <= n;i++) {
res[0][i][i] = 0;
}
for(int stage = 0;stage < n;stage++) {
for(int root = 1;root <= n;root++) {
for(int node = 1;node <= n;node++) {
for(int fin = 1;fin <= n;fin++) {
res[stage + 1][root][fin] = min(res[stage + 1][root][fin],res[stage][root][node] + dis[node][fin]);
}
}
}
}
int k,q;
cin>>k>>q;
k = min(k,n);
while(q--) {
int u,v;
cin>>u>>v;
int kq = INT_MAX;
for(int i = 0;i <= k;i++) {
kq = min(kq,res[i][u][v]);
}
if(kq == INT_MAX) {
cout<<-1<<endl;
} else {
cout<<kq<<endl;
}
}
}
