#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Matrix{
int n;
vector<vector<ll>> v;
Matrix(){}
Matrix(int n) : n(n) {
v = vector<vector<ll>>(n, vector<ll>(n, -1));
}
Matrix operator*(Matrix x){
Matrix y(n);
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
if (v[i][j] == -1) continue;
if (x.v[j][k] == -1) continue;
y.v[i][k] = y.v[i][k] == -1 ? v[i][j]+x.v[j][k] : min(y.v[i][k], v[i][j]+x.v[j][k]);
}
}
}
return y;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int k, n, m, o; cin >> k >> n >> m >> o;
int cmp = (n+k-1)/k;
Matrix up[cmp][16];
for (int i = 0; i < cmp; i++){
for (int j = 0; j < 16; j++){
up[i][j] = Matrix(k);
}
}
for (int i = 0; i < m; i++){
int a, b, t; cin >> a >> b >> t;
up[a/k][0].v[a%k][b%k] = t;
}
for (int i = 1; i < 16; i++){
for (int j = 0; j < cmp; j++){
if ((j+(1<<(i-1))) >= cmp) continue;
up[j][i] = up[j][i-1]*up[j+(1<<(i-1))][i-1];
}
}
for (int i = 0; i < o; i++){
int a, b; cin >> a >> b;
if ((a/k) > (b/k)){
cout << -1 << endl; continue;
}else if ((a/k) == (b/k)){
cout << (a==b ? 0 : -1) << endl;
}else{
int curr = (a/k);
Matrix ans(k);
for (int i = 0; i < k; i++) ans.v[i][i] = 0;
for (int i = 0; i < 16; i++){
if ((1<<i)&((b/k)-(a/k))) ans = ans*up[curr][i], curr += 1<<i;
}
cout << ans.v[a%k][b%k] << endl;
}
}
}
