#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=72;
vector<pair<int,int>>nei[N]={};
int dp[N][N]={};
int ans[N][N];
int n,m;
int lm;
void bfs(int s)
{
for (int i=1;i<=n;i++)
for (int j=0;j<=n;j++)
dp[i][j]=1e12;
dp[s][0]=0;
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
pq.push({0,0,s});
while (pq.size())
{
vector<int>f=pq.top();
pq.pop();
int u=f[2],w=f[0],k=f[1];
if (dp[u][k]!=w) continue;
for (auto [i,w1]:nei[u])
{
if (k+1<=lm&&dp[i][k+1]>w+w1)
{
dp[i][k+1]=w+w1;
pq.push({dp[i][k+1],k+1,i});
}
}
}
for (int i=1;i<=n;i++)
{
int mn=1e18;
for (int j=0;j<=n;j++)
{
mn=min(mn,dp[i][j]);
}
if (mn==1e12)
continue;
ans[s][i]=mn;
}
}
inline void solve()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
dp[i][j]=1e12;
ans[i][j]=-1;
}
dp[i][i]=0;
ans[i][i]=0;
}
for (int i=0;i<m;i++)
{
int a,b,t;
cin>>a>>b>>t;
dp[a][b]=min(dp[a][b],t);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (dp[i][j]!=1e12&&dp[i][j])
nei[i].push_back({j,dp[i][j]});
}
}
int k,q;
cin>>k>>q;
lm=k;
lm=min(lm,n);
for (int i=1;i<=n;i++)
bfs(i);
while (q--)
{
int a,b;
cin>>a>>b;
cout<<ans[a][b]<<'\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
