#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAX_K = 10;
int K;
struct M{
int dist[MAX_K][MAX_K];
M(){
for(int i = 0; i<K; i++){
for(int j = 0; j<K; j++){
dist[i][j] = INF;
}
}
}
void sh(){
/*for(int i = 0; i<K; i++){
for(int j=0; j<K; j++){
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
}
};
M e(){
M res;
for(int i= 0; i<K; i++){
for(int j = 0; j<K; j++){
if(i==j){
res.dist[i][j] = 0;
}
else{
res.dist[i][j] = INF;
}
}
}
return res;
}
M combine(M& lh, M&rh){
M res;
for(int mid= 0; mid<K; mid++){
for(int a = 0; a<K; a++){
for(int b = 0; b<K; b++){
res.dist[a][b] = min(res.dist[a][b], lh.dist[a][mid] + rh.dist[mid][b]);
}
}
}
return res;
}
struct Tree{
vector<M> tree;
void build(vector<M>& v, int lt, int rt, int t){
if(lt == rt){
tree[t] = v[lt];
}
else{
int mid = (lt+rt)/2;
build(v, lt, mid, t*2);
build(v, mid+1, rt, t*2+1);
tree[t] = combine(tree[t*2], tree[t*2+1]);
}
//cout<<"lt "<<lt<<" rt "<<rt<<endl;
tree[t].sh();
}
M get(int l, int r, int lt, int rt, int t){
if(r<lt || rt<l){
return e();
}
else if(l<=lt && rt<=r){
return tree[t];
}
else{
int mid = (lt+rt)/2;
M lh = get(l, r, lt, mid, t*2);
M rh = get(l, r, mid+1, rt, t*2+1);
return combine(lh, rh);
}
}
void sh(){
}
};
signed main(){
int n, m, o;
cin>>K>>n>>m>>o;
int l = (n+K-2)/K;
vector<M> v(l);
for(int i = 0; i<m; i++){
int a,b, t;
cin>>a>>b>>t;
//cout<<"a is "<<a<<endl;
v[a/K].dist[a%K][b%K] = t;
}
Tree tr;
tr.tree.resize(4*l +1);
tr.build(v, 0, l-1, 1);
tr.sh();
for(int i = 0; i<o; i++){
int a, b;
cin>>a>>b;
int res = tr.get(a/K, (b/K)-1, 0, l-1, 1).dist[a%K][b%K];
if(res==INF){
cout<<-1<<endl;
}
else{
cout<<res<<endl;
}
}
}
