#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e6 + 1, M = 1e7 + 1, mod = 1e9 + 7;
const ll INF = 1e18;
ll sp[50001][17][5][5], ans[5][5], tmp[5][5];
int k, n, m, q;
void comb(ll (&t)[5][5], const ll (&a)[5][5], const ll (&b)[5][5]){
for(int x = 0;x < k;x++){
for(int y = 0;y < k;y++){
t[x][y] = INF;
for(int z = 0;z < k;z++){
t[x][y] = min(t[x][y], a[x][z] + b[z][y]);
}
}
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> k >> n >> m >> q;
memset(sp, 0x3f, sizeof(sp));
for(int i = 0, x, y, c;i < m;i++){
cin >> x >> y >> c;
//cerr << x / k << " " << y / k << "\n";
sp[x / k][0][x % k][y % k] = c;
}
for(int i = 1;i < 17;i++){
for(int j = 0;j + (1 << i) < (n + k - 1) / k;j++){
comb(sp[j][i], sp[j][i - 1], sp[j + (1 << (i - 1))][i - 1]);
}
}
for(int l, r;q--;){
cin >> l >> r;
memset(ans, 0x3f, sizeof(ans));
for(int i = 0;i < k;i++) ans[i][i] = 0;
for(int st = l / k, fn = r / k, i = 16;i >= 0;i--){
if(st + (1 << i) <= fn){
//cerr << sp[st][0][l % k][r % k] << "\n";
comb(tmp, ans, sp[st][i]);
memcpy(ans, tmp, sizeof(ans));
st += (1 << i);
}
}
ll z = ans[l % k][r % k];
if(z >= INF)
z = -1;
cout << z << "\n";
}
}
