MAX_N = 50000
MAX_K = 5
MAX_J = 17
INF = float('inf')
def combine(target, a, b, k):
"""
Combine two matrices `a` and `b` into the `target` matrix using
the min-sum product rule, similar to matrix multiplication.
"""
for x in range(k):
for y in range(k):
for z in range(k):
target[x][y] = min(target[x][y], a[x][z] + b[z][y])
k, n, m, o = map(int, input().split())
dp = [[[[INF] * k for _ in range(k)] for _ in range(MAX_J)] for _ in range(MAX_N)]
for _ in range(m):
a, b, t = map(int, input().split())
dp[a // k][0][a % k][b % k] = t
# Precompute dp for all powers of 2 up to 2^16 (binary lifting)
for j in range(1, MAX_J):
for i in range((n + k - 1) // k - (1 << j)):
combine(dp[i][j], dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1], k)
results = []
# Process queries
for _ in range(o):
a, b = map(int, input().split())
ans = [[INF] * k for _ in range(k)]
for i in range(k):
ans[i][i] = 0
curr = a // k
dest = b // k
for i in range(MAX_J - 1, -1, -1):
if curr + (1 << i) <= dest:
tmp = [[INF] * k for _ in range(k)]
combine(tmp, ans, dp[curr][i], k)
ans = tmp
curr += (1 << i)
print(-1 if ans[a % k][b % k] == INF else ans[a % k][b % k])
