#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 50005
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
vector<pair<int, int> > adj[N], q[N];
int dis[N], mx[N];
vector<int> tmp;
int ans[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dis, 0x3f, sizeof dis);
int k, n, m, o;
cin>>k>>n>>m>>o;
while(m--){
int a, b, t;
cin>>a>>b>>t;
adj[a].push_back({b, t});
}
for(int i = 1; i <= o; ++i){
int s, e;
cin>>s>>e;
mx[s] = max(mx[s], e);
q[s].push_back({e, i});
}
for(int i = 0; i < n; ++i){
if(mx[i] < i)
continue;
dis[i] = 0;
for(int j = i; j < mx[i]; ++j){
if(dis[j] == INF)continue;
for(auto& x : adj[j])
if(x.ff <= mx[i])
dis[x.ff] = min(dis[j] + x.ss, dis[x.ff]);
}
for(auto& x : q[i])
ans[x.ss] = (dis[x.ff] == INF ? -1 : dis[x.ff]);
for(int j = i; j <= mx[i]; ++j)
dis[j] = INF;
}
for(int i = 1; i <= o; ++i)
cout<<ans[i]<<'\n';
}
