#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second
const int N = 74, M = 1e9 + 7, LG = 20;
int n , A[N] , m , dis[N][N][N] , q , k , u , v , w;
vector<pair<int,int>> lis[N];
void solve(){
for (int i=0 ; i<N ; i++){
for (int j=0 ; j<N ; j++){
for (int k=0 ; k<N ; k++){
dis[i][j][k] = 1e18;
if (i==j){
dis[i][j][k] = 0;
}
}
}
}
cin >> n >> m;
map<pair<int,int> , int> wi;
for (int i=1 ; i<=m ; i++){
cin >> u >> v >> w;
if (wi[{u,v}] == 0){
wi[{u,v}] = w;
continue;
}
wi[{u,v}] = min(wi[{u,v}] , w);
}
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=n ; j++){
if (!wi[{i,j}]) continue;
lis[i].pb({j , wi[{i,j}]});
}
}
for (int i=1 ; i<=n ; i++){
queue<pair<int,int>> qu;
for (auto j : lis[i]){
qu.push(j);
}
for (int j=1 ; j<=n ; j++){
queue<pair<int,int>> tm;
while(qu.size()){
int v = qu.front().fi , di = qu.front().se;
qu.pop();
dis[i][v][j] = min(dis[i][v][j] , di);
for (auto k : lis[v]){
tm.push({k.fi , k.se + di});
}
}
qu = tm;
}
}
cin >> k >> q;
k = min(k , n);
while(q--){
cin >> u >> v;
int ans = 1e18;
for (int i=0 ; i<=k ; i++){
ans = min(ans , dis[u][v][i]);
}
if (ans == 1e18) ans = -1;
cout << ans << endl;
}
}
signed main(){
// freopen("" , "r" , stdin);
// freopen("" , "w" , stdout);
// cout << setprecision(30);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ts = 1;
// cin >> ts;
while(ts--){
solve();
}
}
