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