#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e15;
int K, N, M, O;
// Qatlamlar orasidagi o'tish matritsasi
struct Matrix {
long long mat[5][5];
Matrix() {
for(int i=0; i<5; ++i)
for(int j=0; j<5; ++j) mat[i][j] = INF;
}
};
// Ikki matritsani birlashtirish (Floyd-Warshall kabi)
Matrix multiply(const Matrix& A, const Matrix& B) {
Matrix C;
for(int i=0; i<K; ++i)
for(int j=0; j<K; ++j)
for(int k=0; k<K; ++k)
C.mat[i][j] = min(C.mat[i][j], A.mat[i][k] + B.mat[k][j]);
return C;
}
Matrix tree[50000]; // Segmentlar daraxti uchun (qatlamlar soni N/K)
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> K >> N >> M >> O;
// Qirralarni o'qish va qatlamlararo matritsalarni to'ldirish
vector<Matrix> adj((N/K) + 1);
for(int i=0; i<M; ++i) {
int u, v, t;
cin >> u >> v >> t;
adj[u/K].mat[u%K][v%K] = t;
}
// Segmentlar daraxtini qurish yoki oddiy DP bilan hisoblash
// (So'rovlar a dan b gacha bo'lgani uchun qatlamlar bo'ylab o'tamiz)
while(O--) {
int a, b;
cin >> a >> b;
if (a/K > b/K) {
cout << -1 << endl;
continue;
}
// Dinamik dasturlash: dp[i] - a dan joriy qatlamdagi i-tugungacha masofa
vector<long long> dp(K, INF);
dp[a%K] = 0;
for (int g = a/K; g < b/K; ++g) {
vector<long long> next_dp(K, INF);
for (int i = 0; i < K; ++i) {
if (dp[i] == INF) continue;
for (int j = 0; j < K; ++j) {
next_dp[j] = min(next_dp[j], dp[i] + adj[g].mat[i][j]);
}
}
dp = next_dp;
}
long long result = dp[b%K];
if (result >= INF) cout << -1 << endl;
else cout << result << endl;
}
return 0;
}
