#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
struct mat
{
vector<vector<int>> a;
int n,m;
mat()
{
n=0,m=0;
}
mat(int _n, int _m)
{
n=_n,m=_m;
vector<int> tmp(m,mod);
ff(i,0,n) a.pb(tmp);
}
mat operator* (mat X)
{
mat ret(n,X.m);
ff(i,0,n) ff(j,0,m) ff(k,0,X.m) ret.a[i][k]=min(ret.a[i][k],a[i][j]+X.a[j][k]);
return ret;
}
} val[135003];
int l[135003],r[135003];
int stk=1;
mat neutral;
mat impo;
mat Sta(int p, int ll, int rr)
{
if (ll>r[p] || rr<l[p]) return neutral;
if (ll<=l[p] && rr>=r[p]) return val[p];
return Sta(2*p,ll,rr)*Sta(2*p+1,ll,rr);
}
int main()
{
FAST;
int k,n,m,q;
cin>>k>>n>>m>>q;
neutral=mat(k,k),impo=neutral;
ff(i,0,k) neutral.a[i][i]=0;
int stn=(n+k-1)/k;
while (stk<stn) stk*=2;
ff(i,0,stk) l[i+stk]=i,r[i+stk]=i;
bff(i,1,stk) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,1,2*stk) val[i]=neutral;
ff(i,0,stn) val[i+stk]=impo;
while (m--)
{
int u,v,w; cin>>u>>v>>w;
val[u/k+stk].a[u%k][v%k]=w;
}
bff(i,1,stk) val[i]=val[2*i]*val[2*i+1];
while (q--)
{
int s,t; cin>>s>>t;
mat T=Sta(1,s/k,t/k-1);
if (s/k==t/k) T=impo;
mat V(1,k);
ff(i,0,k) V.a[0][i]=mod;
V.a[0][s%k]=0;
V=V*T;
if (V.a[0][t%k]>1e9) cout<<-1<<"\n";
else cout<<V.a[0][t%k]<<"\n";
}
}
//Note to self: Check for overflow
