#include <bits/stdc++.h>
using namespace std;
#define SPEED \
ios_base::sync_with_stdio(0); \
cin.tie(NULL); \
cout.tie(NULL);
#define pb push_back
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long
const intt mxN = 2e5 + 5, L = 20, mxA = 1e6 + 35;
void solve() {
int n,m;
cin >> n >> m;
int dp[n+5][n+5][n+5];
int matr[n+5][n+5];
memset(dp,-1,sizeof(dp));
memset(matr,-1,sizeof(matr));
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
if(matr[a][b]==-1) matr[a][b]=c;
else matr[a][b]=min(matr[a][b],c);
}
for(int i=1;i<=n;i++) matr[i][i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j][1]=matr[i][j];
int k,q;
cin >> k >> q;
for(int a = 2; a <= min(k,n); a++){
for(int i = 1; i<= n; i++){
for(int j = 1; j<= n; j++){
for(int u = 1; u<= n; u++){
if(dp[i][u][a-1] == -1 || matr[u][j] == -1) continue;
if(dp[i][j][a] == -1) dp[i][j][a]=dp[i][u][a-1]+matr[u][j];
else dp[i][j][a] = min(dp[i][j][a],dp[i][u][a-1]+matr[u][j]);
}
}
}
}
while(q--){
int a,b;
cin >> a >> b;
int ans = -1;
for(int i = 1;i <= min(k,n);i++){
if(dp[a][b][i] == -1) continue;
if(ans == -1) ans = dp[a][b][i];
else ans = min(ans,dp[a][b][i]);
}
cout << ans << endl;
}
}
int main() {
SPEED;
int tst = 1;
// cin >> tst;
while (tst--) {
solve();
}
return 0;
}
