#include <bits/stdc++.h>
#define x first
#define y second
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=5e4+5;
int n,m,q,k;
vector<tii> edge[N];
struct node{
int d[5][5]={0};
};
node tree[4*N];
void init(int nd,int l,int r){
if(l==r){
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
if(i!=j) tree[nd].d[i][j]=1e9;
}
}
return;
}
int m=(l+r)>>1;
init(nd<<1,l,m); init(nd<<1|1,m+1,r);
for(int i=0;i<k;i++) for(int j=0;j<k;j++){
tree[nd].d[i][j]=1e9;
}
for(auto &it : edge[m]){
int u=get<0>(it)%k,v=get<1>(it)%k,c=get<2>(it);
for(int i=0;i<k;i++) for(int j=0;j<k;j++){
tree[nd].d[i][j]=min(tree[nd].d[i][j],tree[nd<<1].d[i][u]+c+tree[nd<<1|1].d[v][j]);
}
}
}
node qry(int nd,int l,int r,int s,int e){
node res;
if(s<=l&&r<=e) return tree[nd];
int m=(l+r)>>1;
if(e<=m) return qry(nd<<1,l,m,s,e);
if(m<s) return qry(nd<<1|1,m+1,r,s,e);
node n1=qry(nd<<1,l,m,s,e),n2=qry(nd<<1|1,m+1,r,s,e);
for(int i=0;i<k;i++) for(int j=0;j<k;j++){
res.d[i][j]=1e9;
}
for(auto &it : edge[m]){
int u=get<0>(it)%k,v=get<1>(it)%k,c=get<2>(it);
for(int i=0;i<k;i++) for(int j=0;j<k;j++){
res.d[i][j]=min(res.d[i][j],n1.d[i][u]+c+n2.d[v][j]);
}
}
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>k>>n>>m>>q;
for(int u,v,c,i=1;i<=m;i++){
cin>>u>>v>>c;
edge[u/k].emplace_back(u,v,c);
}
init(1,0,(n-1)/k);
for(int u,v,i=1;i<=q;i++){
cin>>u>>v;
if(u/k>=v/k){
cout<<"-1\n";
continue;
}
node res=qry(1,0,(n-1)/k,u/k,v/k);
if(res.d[u%k][v%k]==1e9) cout<<"-1\n";
else cout<<res.d[u%k][v%k]<<"\n";
}
return 0;
}
