#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define ppll pair<ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
#define LOCALIO "C:/Users/admin/Documents/Code/"
ll A[100][100];
ll dp[100][100][100];
int main()
{
#ifdef LOCAL
freopen( LOCALIO "input.txt","r",stdin) ;
freopen( LOCALIO "output.txt","w",stdout) ;
#endif
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
// freopen("FIBONACCI.inp","r",stdin);
// freopen("FIBONACCI.out","w",stdout);
ll n, m; cin >> n >> m;
for (ll i=1; i<=n; i++)
for (ll j=1; j<=n; j++)
{
A[i][j]=1e18;
for (ll k=0; k<=n; k++)
dp[i][j][k]=1e18;
}
for (ll i=1; i<=m; i++)
{
ll u, v, w; cin >> u >> v >> w;
A[u][v]=min(A[u][v], w);
}
for (ll i=1; i<=n; i++)
dp[i][i][0]=0;
for (ll i=1; i<=n; i++)
for (ll j=1; j<=n; j++)
for (ll k=1; k<=n; k++)
for (ll z=1; z<=n; z++)
dp[j][k][i]=min(dp[j][k][i], dp[j][z][i-1]+A[z][k]);
ll k, q; cin >> k >> q;
for (ll i=1; i<=q; i++)
{
ll u, v; cin >> u >> v;
ll ans=1e18;
for (ll j=0; j<=min(k, n); j++)
ans=min(ans, dp[u][v][j]);
if (ans>1e17)
cout << -1;
else cout << ans;
cout << "\n";
}
}
