#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 5e4 + 5;
const int oo = 1e9;
int dis[16][N][5];
int lca[16][N][5];
int n,k,m,q;
void build()
{
for (int j = 1; j < 16; j++)
for (int i = 0; i < n; i++)
{
for (int cur = 0; cur < k; cur++)
{
int p = lca[j - 1][i][cur];
if (p < 0)
continue;
for (int nxt = 0; nxt < k; nxt++)
{
int pp = lca[j - 1][p][nxt];
if (pp < 0)
continue;
lca[j][i][nxt] = pp;
dis[j][i][nxt] = min(dis[j][i][nxt], dis[j - 1][i][cur] + dis[j - 1][p][nxt]);
}
}
}
}
void jump(vector <pair <int, int>> &f, int step)
{
for (int i = 0; i < 16; i++) if ((step >> i) & 1)
{
vector <pair <int, int>> g(k, mp(oo, oo));
for (auto pir : f)
{
int u = pir.fi;
int cur = pir.se;
if (u == oo)
continue;
for (int nxt = 0; nxt < k; nxt++)
{
int v = lca[i][u][nxt];
if (v < 0)
continue;
g[nxt] = min(g[nxt], mp(v, cur + dis[i][u][nxt]));
}
}
f = g;
}
}
int solve(int s, int t)
{
int step = (t / k) - (s / k);
if (step < 0)
return -1;
vector <pair <int, int>> res(k, mp(oo, oo));
res[s % k] = mp(s, 0);
jump(res, step);
for (auto pir : res)
if (pir.fi == t)
return pir.se;
return -1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.inp","r",stdin);
cin >> k >> n >> m >> q;
memset(lca, -1, sizeof(lca));
for (int j = 0; j < 16; j++)
for (int i = 0; i < n; i++)
for (int cur = 0; cur < k; cur++)
dis[j][i][cur] = oo;
for (int i = 1; i <= m; i++)
{
int u,v,w;
cin >> u >> v >> w;
lca[0][u][v % k] = v;
dis[0][u][v % k] = w;
}
build();
while (q--)
{
int u,v;
cin >> u >> v;
cout << solve(u, v) << "\n";
}
return 0;
}
