#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
const int N=1e5+10;
const ll MOD=1e9+7;
int k,n,m,o;
struct node{
int a[5][5];
node(){
FOR(i,5)FOR(j,5)a[i][j]=INT_MAX;
}
void operator=(node t){
FOR(i,5)FOR(j,5)a[i][j]=t.a[i][j];
}
}sg[4*N],zro;
node mrg(node a,node b){
if (b.a[0][0]==-1)return a;
if (a.a[0][0]==-1)return b;
node c;
FOR(i,k){
FOR(j,k){
c.a[i][j]=INT_MAX;
}
}
FOR(i,k){
FOR(j,k){
FOR(mj,5){
if (a.a[i][mj]==INT_MAX)continue;
if (b.a[mj][j]==INT_MAX)continue;
c.a[i][j]=min(c.a[i][j],a.a[i][mj]+b.a[mj][j]);
}
}
}
return c;
}
vector<pir> g[N];
void build(int v,int tl,int tr){
//sg[v]=new node();
if (tl==tr){
FOR(i,k){
trav(to,g[tl*k+i]){
//cout<<"heey "<<sg[v].a[i][to.fr%k]<<endl;
sg[v].a[i][to.fr%k]=to.sc;
}
}
/*
cout<<v<<" "<<tl<<" "<<tr<<endl;
FOR(i,k){
FOR(j,k){
cout<<sg[v].a[i][j]<<" ";
}
cout<<endl;
}
cout<<"************"<<endl;*/
return;
}
int tm=(tl+tr)/2;
build(v+v,tl,tm);
build(v+v+1,tm+1,tr);
sg[v]=mrg(sg[v+v],sg[v+v+1]);
/*
cout<<v<<" "<<tl<<" "<<tr<<endl;;
FOR(i,k){
FOR(j,k){
cout<<sg[v].a[i][j]<<" ";
}
cout<<endl;
}
cout<<"************"<<endl;*/
}
node query(int v,int tl,int tr,int l,int r){
//cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
if (l>r) return zro;
if (tl==l && tr==r)return sg[v];
int tm=(tl+tr)/2;
return mrg(query(v+v,tl,tm,l,min(tm,r)),query(v+v+1,tm+1,tr,max(tm+1,l),r));
}
int main(){
fastio;
srng;
//cout<<zro.a[1][1]<<endl;
//zro=new node();
cin>>k>>n>>m>>o;
FOR(i,m){
int a,b,c;
cin>>a>>b>>c;
g[a].ad({b,c});
//g[b].ad({a,c});
}
zro.a[0][0]=-1;
while(n%k)n++;
int qan=n/k;
build(1,0,qan);
FOR(i,o){
int l,r;
cin>>l>>r;
if (l/k>=r/k){
cout<<-1<<endl;
continue;
}
node tv=query(1,0,qan,l/k,r/k-1);
if (tv.a[l%k][r%k]==INT_MAX)cout<<-1<<endl;
else cout<<tv.a[l%k][r%k]<<endl;
}
return 0;
}
