#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 50005
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define LEN 240
int fl[250][240][240];
vector<pair<pair<int, int>, int> > tr[250], buck[250];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, n, m, o;
cin>>k>>n>>m>>o;
memset(fl, 0x3f, sizeof fl);
for(int i = 0; i < 210; ++i)
for(int j = 0; j < 240; ++j)
fl[i][j][j] = 0;
while(m--){
int a, b, t;
cin>>a>>b>>t;
if(a / LEN != b / LEN){
tr[a / LEN].push_back({{a % k, b % k}, t});
} else {
buck[a / LEN].push_back({{a % LEN, b % LEN}, t});
}
}
for(int i = 0; i < 210; ++i){
sort(buck[i].begin(), buck[i].end(), [](const pair<pair<int, int>, int>& lhs, const pair<pair<int, int>, int>& rhs){
return lhs.ff.ss < rhs.ff.ss;
});
for(auto& x : buck[i]){
for(int j = 0; j <= x.ff.ff; ++j){
fl[i][j][x.ff.ss] = min(fl[i][j][x.ff.ss], fl[i][j][x.ff.ff] + x.ss);
}
}
}
while(o--){
int a, b;
cin>>a>>b;
int ans = INF;
if(a / LEN == b / LEN){
ans = fl[a / LEN][a % LEN][b % LEN];
} else {
vector<int> tmp(k);
for(int i = 0; i < k; ++i){
tmp[i] = fl[a / LEN][a % LEN][LEN - k + i];
}
vector<int> tmp3(k, INF);
for(auto& x : tr[a / LEN])
tmp3[x.ff.ss] = min(tmp3[x.ff.ss], tmp[x.ff.ff] + x.ss);
swap(tmp, tmp3);
for(int i = a / LEN + 1; i < b / LEN; ++i){
vector<int> tmp2(k, INF);
for(int j = 0; j < k; ++j){
for(int l = 0; l < k; ++l){
tmp2[l] = min(tmp2[l], tmp[j] + fl[i][j][LEN - k + l]);
}
}
swap(tmp, tmp2);
vector<int> tmp4(k, INF);
for(auto& x : tr[i])
tmp4[x.ff.ss] = min(tmp4[x.ff.ss], tmp[x.ff.ff] + x.ss);
swap(tmp, tmp4);
}
for(int i = 0; i < k; i++){
ans = min(ans, tmp[i] + fl[b / LEN][i][b % LEN]);
}
}
cout<<(ans == INF ? -1 : ans)<<'\n';
}
}
