/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
struct node
{
LL d[6][6];
node()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
d[i][j]=mod*100005ll;
}
};
LL k,n,m,o;
bool used[50004];
vector<int> a[50004];
vector<pair<int,LL>> g[50004];
node t[4*50004];
node merge(node a,node b,int pos)
{
node r;
for(int s=0;s<k;s++)
for(int e=0;e<k;e++)
for(int v=pos*k;v<pos*k+k;v++)
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
LL d=g[v][i].second;
r.d[s][e]=min( a.d[s][v-pos*k]+b.d[to-pos*k-k][e]+d ,r.d[s][e]);
}
return r;
}
void build(int v,int l,int r)
{
if(l==r)
{
for(int i=0;i<k;i++)
t[v].d[i][i]=0;
return;
}
int m=(l+r)/2;
build(v*2,l,m);
build(v*2+1,m+1,r);
t[v]=merge(t[v*2],t[v*2+1],m);
}
node get(int v,int l,int r,int i,int j)
{
if(i>j)
return node();
if(l==i && r==j)
return t[v];
int m=(l+r)/2;
if(j<=m)
return get(v*2,l,m,i,j);
else if(i>=m+1)
return get(v*2+1,m+1,r,i,j);
else
return merge(
get(v*2,l,m,i,m),
get(v*2+1,m+1,r,m+1,j),
m
);
}
int main()
{
cin>>k>>n>>m>>o;
while(m--)
{
int a,b;
LL d;
scanf("%d%d%lld",&a,&b,&d);
g[a].PB(MP(b,d));
}
for(int i=0;i<n;i++)
a[i/k].PB(i);
n--;
build(1,0,n/k);
while(o--)
{
int a,b;
scanf("%d%d",&a,&b);
LL ans=get(1,0,n/k,a/k,b/k).d[a-(a/k)*k][b-(b/k)*k];
if(ans>=mod*100005ll)
ans=-1;
printf("%lld\n",ans);
}
return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/
