#include<bits/stdc++.h>
#define inf 1000000000
#define pi pair<int,int>
#define fi first
#define se second
#define maxn 50005
#define maxk 10
using namespace std;
int k,n,m,q;
int dp[maxn][maxk];
vector<pi>in[maxn];
vector<pi>out[maxn];
int idb(int i)
{
return i/k;
}
int lb(int i)
{
return i*k;
}
int rb(int i)
{
return min(n-1,(i+1)*k-1);
}
struct node
{
int s,t,id;
node(int s=0,int t=0,int id=0)
{
this->s=s;
this->t=t;
this->id=id;
}
};
int ans[maxn];
void dnc(int l,int r,vector<node>&Query)
{
if(l>r)return ;
if(l==r)
{
for(auto[s,t,id]:Query)
{
ans[id]=inf;
}
return;
}
int mid=(l+r)/2;
for(int i=l;i<=r;i++)
{
for(int u=lb(i);u<=rb(i);u++)
{
for(int v=0;v<k;v++)
{
dp[u][v]=inf;
}
}
}
for(int u=lb(mid);u<=rb(mid);u++)
{
dp[u][u%k]=0;
}
for(int i=mid-1;i>=l;i--)
{
for(int u=lb(i);u<=rb(i);u++)
{
for(int t=0;t<k;t++)
{
for(auto[v,w]:out[u])
{
dp[u][t]=min(dp[u][t],dp[v][t]+w);
}
}
}
}
for(int i=mid+1;i<=r;i++)
{
for(int u=lb(i);u<=rb(i);u++)
{
for(int t=0;t<k;t++)
{
for(auto[v,w]:in[u])
{
dp[u][t]=min(dp[u][t],dp[v][t]+w);
}
}
}
}
vector<node>QueryL;
vector<node>QueryR;
for(auto[s,t,id]:Query)
{
if(idb(t)<mid)QueryL.push_back(node(s,t,id));
else if(idb(s)>mid)QueryR.push_back(node(s,t,id));
else
{
if(idb(s)==idb(t))ans[id]=inf;
else
{
ans[id]=inf;
for(int x=0;x<k;x++)
{
ans[id]=min(ans[id],dp[s][x]+dp[t][x]);
}
}
}
}
dnc(l,mid-1,QueryL);
dnc(mid+1,r,QueryR);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>k>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
out[u].push_back({v,w});
in[v].push_back({u,w});
}
vector<node>Query;
for(int i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
if(idb(u)>=idb(v))ans[i]=inf;
else
{
Query.push_back(node(u,v,i));
}
}
dnc(0,idb(n),Query);
for(int i=1;i<=q;i++)
{
if(ans[i]==inf)cout<<-1<<'\n';
else cout<<ans[i]<<'\n';
}
}
