#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=71, inf=4e18;
ll n, m, k, q, u, v, w, dist[nx][nx], dp[nx][nx][nx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dist[i][j]=dp[0][i][j]=inf;
for (int i=1; i<=m; i++) cin>>u>>v>>w, dist[u][v]=min(dist[u][v], w);
cin>>k>>q;
k=min(k, n);
for (int i=1; i<=n; i++) dp[0][i][i]=0;
for (int i=1; i<=k; i++)
{
for (int u=1; u<=n; u++)
{
for (int v=1; v<=n; v++)
{
dp[i][u][v]=dp[i-1][u][v];
for (int md=1; md<=n; md++) dp[i][u][v]=min(dp[i][u][v], dp[i-1][u][md]+dist[md][v]);
}
}
}
while (q--)
{
cin>>u>>v;
if (dp[k][u][v]==inf) cout<<-1<<'\n';
else cout<<dp[k][u][v]<<'\n';
}
}
