#include <bits/stdc++.h>
using namespace std;
int n,k,q;
vector<pair<int,int>>g[50000],que;
vector<int>ans,pom[5];
void daq(int l,int r,vector<int>v)
{
if(l/k==r/k||l>r)
{
return;
}
int m=((l+r)/2)/k;
for(int i=m*k+1;i<=r;i++)
{
for(int j=0;j<k;j++)
{
pom[j][i]=INT_MAX;
}
}
for(int i=min(m*k,l);i<=r;i++)
{
if(i/k==m)
{
for(int j=0;j<k;j++)
{
if(j==i-m*k)
{
pom[j][i]=0;
}
else
{
pom[j][i]=INT_MAX;
}
}
}
for(auto p:g[i])
{
if(p.first>r)continue;
for(int j=0;j<k;j++)
{
if(pom[j][i]!=INT_MAX)
{
pom[j][p.first]=min(pom[j][i]+p.second,pom[j][p.first]);
}
}
}
}
for(int i=m*k-1;i>=l;i--)
{
for(int j=0;j<k;j++)
{
pom[j][i]=INT_MAX;
}
for(auto p:g[i])
{
for(int j=0;j<k;j++)
{
if(pom[j][p.first]!=INT_MAX)
{
pom[j][i]=min(pom[j][i],pom[j][p.first]+p.second);
}
}
}
}
vector<int>todo1,todo2;
for(auto i:v)
{
auto p=que[i];
if(p.first<m*k&&p.second>=(m+1)*k)
{
int res=INT_MAX;
for(int j=0;j<k;j++)
{
if(pom[j][p.first]!=INT_MAX&&pom[j][p.second]!=INT_MAX)
{
res=min(res,pom[j][p.first]+pom[j][p.second]);
}
}
if(res!=INT_MAX)ans[i]=res;
}
else if(p.first/k==m&&p.second>=(m+1)*k)
{
if(pom[p.first%k][p.second]!=INT_MAX)
{
ans[i]=pom[p.first%k][p.second];
}
}
else if(p.second/k==m&&p.first<m*k)
{
if(pom[p.second%k][p.first]!=INT_MAX)
{
ans[i]=pom[p.second%k][p.first];
}
}
else if(p.second/k<m)
{
todo1.push_back(i);
}
else if(p.first/k>m)
{
todo2.push_back(i);
}
}
m=(l+r)/2;
daq(l,m,todo1);
daq(m+1,r,todo2);
}
int main()
{
int m,a,b,c;
cin>>k>>n>>m>>q;
vector<int>todo;
for(int i=0;i<k;i++)
{
pom[i].resize(n);
}
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=0;i<q;i++)
{
ans.push_back(-1);
cin>>a>>b;
que.push_back({a,b});
if(a/k!=b/k)
{
todo.push_back(i);
}
}
daq(0,n-1,todo);
for(int i=0;i<q;i++)
{
cout<<ans[i]<<endl;
}
}
