#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
typedef long double ld;
const int maxn = 75;
const ll inf = 1e18+5;
int n, m, k, q;
ll d[75][75][75];
ll adj[75][75];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == j)adj[i][j] = 0;
else adj[i][j] = inf;
}
}
for(int i = 0; i < m; i++){
int a, b, w;
cin >> a >> b >> w;
adj[a][b] = min<ll>(adj[a][b], w);
}
cin >> k >> q;
k = min(k, n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int l = 0; l <= k; l++){
if(l == 0 && i == j)d[i][j][l] = 0;
else d[i][j][l] = inf;
}
}
}
for(int l = 1; l <= k; l++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int v = 1; v <= n; v++){
d[i][j][l] = min(d[i][j][l], d[i][v][l-1] + adj[v][j]);
}
}
}
}
while(q--){
int a, b;
cin >> a >> b;
if(d[a][b][k] >= inf)cout << "-1";
else cout << d[a][b][k];
cout << "\n";
}
}
