#include <bits/stdc++.h>
#define el '\n'
#define FNAME "fee"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
const int MAXN = 50'005;
const int LOG = 16;
const long long INF = (long long) 1e16 + 15092007;
struct Matrix{
int n,m;
vector<vector<long long>> matrix;
Matrix(int N=0,int M=0){
n=N;
m=M;
if (n>0 and m>0){
matrix.assign(n,vector<long long>(m,INF));
}
}
inline void toUnit(){
for (int i=0;i<n;i++) matrix[i][i]=0;
}
Matrix operator * (const Matrix &other) const{
Matrix res(n,other.m);
for (int i=0;i<n;i++){
for (int j=0;j<other.m;j++){
for (int k=0;k<m;k++){
minimize(res.matrix[i][j],matrix[i][k] + other.matrix[k][j]);
}
}
}
return res;
}
};
int K,n,m,q;
int BLK;
// ? dp[i].matrix[x][y]: min cost to go from i * K + x -> (i+1)*K + y
vector<Matrix> dp;
void init(){
cin>>K>>n>>m>>q;
BLK = (n+K-1) / K;
dp.assign(BLK,Matrix(K,K));
for (int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
dp[u / K].matrix[u % K][v % K] = w;
}
}
struct SegmentTree{
int n;
vector<Matrix> st;
SegmentTree(int N=0){
n = N;
if (n>0){
st.resize(4 * n + 4,Matrix(K,K));
}
}
void build(int node,int l,int r,const vector<Matrix> &a){
if (l==r){
st[node] = a[l];
return;
}
int mid = (l+r)>>1;
build(2*node,l,mid,a);
build(2*node+1,mid+1,r,a);
st[node] = st[2*node] * st[2*node+1];
}
void build(const vector<Matrix> &a){
build(1,0,n-1,a);
}
Matrix getMatrix(int node,int l,int r,int wanted_l,int wanted_r){
if (wanted_r < l or r < wanted_l){
Matrix unitMatrix(K,K);
unitMatrix.toUnit();
return unitMatrix;
}
if (wanted_l <= l and r <= wanted_r) return st[node];
int mid = (l+r)>>1;
return getMatrix(2*node,l,mid,wanted_l,wanted_r) * getMatrix(2*node+1,mid+1,r,wanted_l,wanted_r);
}
Matrix getMatrix(int l,int r){
return getMatrix(1,0,n-1,l,r);
}
};
void sol(){
SegmentTree st(BLK);
st.build(dp);
while (q--){
int u,v;
cin>>u>>v;
if (u==v){
cout<<0<<el;
continue;
}
if ((u/K) >= (v/K)){
cout<<-1<<el;
continue;
}
int L = u / K;
int R = v / K;
long long res = st.getMatrix(L,R-1).matrix[u % K][v % K];
cout<< (res == INF ? -1 : res)<<el;
}
}
int main(){
setup();
init();
sol();
}
