#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int n,m;
cin>>n>>m;
int nei[n+1][n+1];
vector<vector<int>> dis(n+1,vector<int>(n+1));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
nei[i][j]=dis[i][j]=(i!=j)*inf;
for (int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
nei[a][b]=min(nei[a][b],c);
}
int k,q;
cin>>k>>q;
k=min(k,n-1);
for (int i=0;i<k;i++)
{
vector<vector<int>> dis1=dis;
for (int i=1;i<=n;i++)
for (int p=1;p<=n;p++)
for (int j=1;j<=n;j++)
dis1[i][j]=min(dis1[i][j],nei[i][p]+dis[p][j]);
dis=dis1;
}
while (q--)
{
int a,b;
cin>>a>>b;
cout<<(dis[a][b]<inf?dis[a][b]:-1)<<endl;
}
return 0;
}
