// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
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 , wi[N][N];
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] = 1e9;
if (i==j){
dis[i][j][k] = 0;
}
}
}
}
cin >> n >> m;
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;
queue<pair<int,int>> tm;
for (auto j : lis[i]){
qu.push(j);
}
for (int j=1 ; j<=n ; j++){
if (j&1){
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});
}
}
}else{
while(tm.size()){
int v = tm.front().fi , di = tm.front().se;
tm.pop();
dis[i][v][j] = min(dis[i][v][j] , di);
for (auto k : lis[v]){
qu.push({k.fi , k.se + di});
}
}
}
}
}
cin >> k >> q;
k = min(k , n);
while(q--){
cin >> u >> v;
int ans = 1e9;
for (int i=0 ; i<=k ; i++){
ans = min(ans , dis[u][v][i]);
}
if (ans == 1e9) 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();
}
}
