// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 5e4 + 5;
const int M = 1e6 + 5;
const int LG = 18;
const int C = 26;
const long long INF = 1e18;
const int B = 320;
const int P = 31;
const int MOD = 1e9 + 7;
int k, n, m, q, mask[N], mid[LG][N];
long long val[LG][N][6][6];
vector<pair<int, int>> adj[N];
void build(int l, int r, int lvl)
{
if (l == r)
{
return;
}
int m = (l + r) / 2;
// cout << l << " " << r << " " << lvl << "\n";
for (int x = 0; x < k; x++)
{
val[lvl][m][x][x] = 0;
}
for (int x = m - 1; x >= l; x--)
{
for (int y = 0; y < k; y++)
{
for (int z = 0; z < k; z++)
{
for (auto &[i, w] : adj[x * k + y])
{
val[lvl][x][y][z] = min(val[lvl][x][y][z], val[lvl][x + 1][i % k][z] + w);
}
// cout << val[lvl][x][y][z] << " " << lvl << " " << x << " " << x * k + y << " " << (x + 1) * k + z << "\n";
}
}
}
for (int x = 0; x < k; x++)
{
val[lvl][m + 1][x][x] = 0;
}
for (int x = m + 1; x < r; x++)
{
for (int y = 0; y < k; y++)
{
for (int z = 0; z < k; z++)
{
for (auto &[i, w] : adj[x * k + y])
{
val[lvl][x + 1][y][z] = min(val[lvl][x + 1][y][z], val[lvl][x][i % k][z] + w);
}
}
}
}
for (int x = m + 1; x <= r; x++)
{
mask[x] |= 1 << lvl;
}
for (int x = l; x <= r; x++)
{
mid[lvl][x] = m;
}
build(l, m, lvl + 1);
build(m + 1, r, lvl + 1);
}
void solve()
{
cin >> k >> n >> m >> q;
for (int x = 0; x <= n; x++)
{
for (int y = 0; y < LG; y++)
{
for (int z = 0; z < k; z++)
{
for (int t = 0; t < k; t++)
{
val[x][y][z][t] = INF;
}
}
}
}
for (int x = 0; x < m; x++)
{
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
}
build(0, n / k, 0);
for (int x = 0; x < q; x++)
{
int a, b;
cin >> a >> b;
if (a / k == b / k)
{
if (a == b)
cout << 0 << "\n";
else
cout << -1 << "\n";
continue;
}
int i = __builtin_ctz(mask[a / k] ^ mask[b / k]);
// cout << i << " ";
long long ans = INF;
int m = mid[i][a / k];
// cout << m << " " << a << " " << b << "\n";
for (int y = 0; y < k; y++)
{
for (auto &[j, w] : adj[m * k + y])
{
// cout << m * k + y << " " << i << " " << a / k << " " << a % k << " " << y << " " << i % k << " " << b % k << "\n";
// cout << val[i][a / k][a % k][y] << " " << val[i][b / k][i % k][b % k] << "v\n";
ans = min(ans, val[i][a / k][a % k][y] + val[i][b / k][j % k][b % k] + w);
}
}
if (ans == INF)
cout << -1 << "\n";
else
cout << ans << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}
