#include <bits/stdc++.h>
using namespace std;
#define ll long long
template<class T>
inline bool minimize(T &a, const T &b) {return (a > b ? a = b, 1 : 0);}
template<class T>
inline bool maximize(T &a, const T &b) {return (a < b ? a = b, 1 : 0);}
const int N = 5e4 + 5;
const int LG = 18;
int n, m, k, q;
int f[N][LG][5][5], ans[5][5], tmp[5][5], inf;
void calc(int g[5][5], int a[5][5], int b[5][5]){
for (int x = 0; x < k; ++x)
for (int y = 0; y < k; ++y)
for (int z = 0; z < k; ++z)
minimize(g[x][y], a[x][z] + b[z][y]);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
memset(f, 0x3f, sizeof f);
inf = f[0][0][0][0];
while (m--){
int u, v, w;
cin >> u >> v >> w;
f[u / k][0][u % k][v % k] = w;
}
for (int j = 1; j < LG; ++j)
for (int i = 0; i + (1 << j) < (n + k - 1) / k; ++i)
calc(f[i][j], f[i][j-1], f[i + (1 << (j-1))][j-1]);
while (q--){
int u, v;
cin >> u >> v;
memset(ans, 0x3f, sizeof ans);
for (int i = 0; i < k; ++i) ans[i][i] = 0;
for (int x = u / k, y = v / k, i = 17; ~i; --i)
if (x + (1 << i) <= y){
memset(tmp, 0x3f, sizeof tmp);
calc(tmp, ans, f[x][i]);
memcpy(ans, tmp, sizeof ans);
x += (1 << i);
}
cout << (ans[u % k][v % k] == inf ? -1 : ans[u % k][v % k]) << '\n';
}
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 1
*/
