#include <bits/stdc++.h>
using namespace std;
long long l(long long x) { return (x << 1); }
long long r(long long x) { return (x << 1) + 1; }
void setup(long long L, long long R, vector<vector<vector<long long>>> &dp, long long x, long long K)
{
if (L == R)
return;
long long m = (L + R) / 2;
setup(L, m, dp, l(x), K);
setup(m + 1, R, dp, r(x), K);
for (long long i = 0; i < K; i++)
{
for (long long j = 0; j < K; j++)
{
for (long long k = 0; k < K; k++)
{
dp[x][i][j] = min(dp[x][i][j], dp[l(x)][i][k] + dp[r(x)][k][j]);
}
}
}
}
vector<vector<long long>> query(long long L, long long R, long long a, long long b, long long x, long long K, vector<vector<vector<long long>>> &dp)
{
vector<vector<long long>> ans;
if (L > b || R < a)
return ans;
ans.assign(K, vector<long long>(K, 1000000000000));
if (L >= a && R <= b)
return dp[x];
long long m = (L + R) / 2;
vector<vector<long long>> lef = query(L, m, a, b, l(x), K, dp);
vector<vector<long long>> right = query(m + 1, R, a, b, r(x), K, dp);
if (lef.size() == 0)
ans = right;
else if (right.size() == 0)
ans = lef;
else
for (long long i = 0; i < K; i++)
{
for (long long j = 0; j < K; j++)
{
for (long long k = 0; k < K; k++)
{
ans[i][j] = min(ans[i][j], lef[i][k] + right[k][j]);
}
}
}
return ans;
}
int main()
{
long long N, M, K, O;
cin >> K >> N >> M >> O;
long long N2 = (1 << (long long)ceil(log2(ceil((double)N / K))));
vector<vector<vector<long long>>> dp(2 * N2, vector<vector<long long>>(K, vector<long long>(K, 1000000000000)));
for (long long i = 0; i < M; i++)
{
long long a, b, t;
cin >> a >> b >> t;
dp[N2 + a / K][a % K][b % K] = t;
}
setup(0, N2 - 1, dp, 1, K);
for (long long i = 0; i < O; i++)
{
long long a, b;
cin >> a >> b;
if (a / K == b / K)
{
cout << -1 << '\n';
continue;
}
vector<vector<long long>> temp = query(0, N2 - 1, a / K, b / K - 1, 1, K, dp);
cout << ((temp[a % K][b % K] == 1000000000000) ? -1 : temp[a % K][b % K]) << '\n';
}
}
