#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <functional>
#include <iomanip>
#include <sstream>
#include <numeric>
#define int long long
#define pb push_back
#define be begin()
#define en end()
#define fi first
#define se second
#define makep make_pair
using namespace std;
int mod=1e9+7;
void ai(vector<int> &v){
for(auto &go : v){
cin>>go;
}
}
void yesno(int k){
if(k==1){
cout<<"Yes";
}
else{
cout<<"No";
}
}
int bfs(int node,int hedef,int n,int k,vector<vector<int>> &adjm){
vector<vector<int>> miu(n,vector<int>(71,1e10));
miu[node][0]=0;
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
pq.push({0,{0,node}});
while(pq.size()){
int cost=pq.top().first;
node=pq.top().second.second;
int uzunluk=pq.top().second.first;
pq.pop();
if(cost>miu[node][uzunluk]){
continue;
}
for(int go=0;go<n;go++){
if(go!=node&&miu[go][uzunluk+1]>cost+adjm[node][go]&&uzunluk<k){
miu[go][uzunluk+1]=cost+adjm[node][go];
pq.push({cost+adjm[node][go],{uzunluk+1,go}});
}
}
}
int cevap=1e10;
for(int i=0;i<=70;i++){
cevap=min(cevap,miu[hedef][i]);
}
if(cevap==1e10){
cevap=-1;
}
return cevap;
}
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>> adjm(n,vector<int>(n,1e10));
while(m--){
int a,b,t;
cin>>a>>b>>t;
a--;
b--;
if(t<adjm[a][b]){
adjm[a][b]=t;
}
}
int k,q;
cin>>k>>q;
while(q--){
int c,d;
cin>>c>>d;
c--;
d--;
cout<<bfs(c,d,n,k,adjm)<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int te=1;
//cin>>te;
while(te--){
solve();
}
}
