#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 50000, INF = 1e18;
struct matrix{
int M, N, grid[5][5];
void init(int x, int y, int val){
M = x, N = y;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
grid[i][j] = val;
}
matrix operator * (matrix b){
matrix a = *this;
matrix c;
c.init(a.M, b.N, +INF);
for (int i = 0; i < c.M; i++)
for (int j = 0; j < c.N; j++)
for (int k = 0; k < a.N; k++)
c.grid[i][j] = min(c.grid[i][j], a.grid[i][k]+b.grid[k][j]);
return c;
}
};
int K, N, M, O, nLayer;
map <pii, int> d;
matrix A[NM+5];
matrix st[4*NM+5];
int Layer(int a){
return a/K;
}
int dist(int a, int b){
if (a == b) return 0;
if (d.count(mp(a, b)) == 0) return +INF;
return d[mp(a, b)];
}
matrix iden(int k){
matrix a;
a.init(k, k, +INF);
for (int i = 0; i < k; i++)
a.grid[i][i] = 0;
return a;
}
void build(int id, int l, int r){
st[id].init(K, K, 0);
if (l == r){
st[id] = A[l];
return;
}
int mid = (l+r)/2;
build(2*id, l, mid);
build(2*id+1, mid+1, r);
st[id] = st[2*id]*st[2*id+1];
}
matrix get(int id, int l, int r, int u, int v){
if (u > v || v < l || u > r) return iden(K);
if (l >= u && r <= v) return st[id];
int mid = (l+r)/2;
return get(2*id, l, mid, u, v)*get(2*id+1, mid+1, r, u, v);
}
void solveQuery(int a, int b){
if (Layer(a) >= Layer(b)){
cout << "-1\n";
return;
}
int l = Layer(a), r = Layer(b);
matrix C; C.init(1, K, +INF);
for (int i = 0; i < K; i++)
C.grid[0][i] = dist(a, (l+1)*K+i);
C = C*get(1, 0, nLayer-2, l+1, r-1);
int ans = C.grid[0][b%K];
if (ans >= +INF) ans = -1;
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> K >> N >> M >> O;
nLayer = N/K+1;
for (int i = 0; i < nLayer; i++)
A[i].init(K, K, +INF);
while (M--){
int a, b, t;
cin >> a >> b >> t;
d[mp(a, b)] = t;
int k = Layer(a);
A[k].grid[a%K][b%K] = t;
}
build(1, 0, nLayer-2);
while (O--){
int a, b;
cin >> a >> b;
solveQuery(a, b);
}
return 0;
}
