#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
struct m
{
vector<vector<ll>>a;
m()
{
a.assign(n,vector<ll>(n,2e18));
}
};
m f(m x,m y)
{
m z;
for(ll i=0;i<n;i++)
{
for(ll k=0;k<n;k++)
{
if(x.a[i][k]>1e18)
{
continue;
}
for(ll j=0;j<n;j++)
{
if(y.a[k][j]>1e18)
{
continue;
}
z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]);
}
}
}
return z;
}
void f()
{
ll e,k,q;
cin>>n>>e;
m b;
for(ll i=0;i<n;i++)
{
b.a[i][i]=0;
}
for(ll i=0;i<e;i++)
{
ll u,v,w;
cin>>u>>v>>w;
u--;v--;
b.a[u][v]=min(b.a[u][v],w);
}
cin>>k>>q;
m r;
for(ll i=0;i<n;i++)
{
r.a[i][i]=0;
}
while(k>0)
{
if(k&1)
{
r=f(r,b);
}
b=f(b,b);
k>>=1;
}
for(ll i=0;i<q;i++)
{
ll s,d;
cin>>s>>d;
s--;d--;
if(r.a[s][d]>1e18)
{
cout<<-1<<endl;
}
else
{
cout<<r.a[s][d]<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
f();
return 0;
}
