#include <bits/stdc++.h>
using namespace std;
const int sz = 5e4+5;
const int inf = 1e9+7;
vector<pair<int, int>> g[sz];
vector<int> dis(sz, inf);
void dijkstra(int node){
fill(dis.begin(), dis.begin()+sz+1, inf);
dis[node] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, node});
while ( !q.empty()){
auto [c, curr] = q.top();
q.pop();
for(auto [v, w]: g[curr]){
if(dis[v] > dis[curr] + w){
dis[v] = dis[curr] + w;
q.push({dis[v], v});
}
}
}
}
signed main(){
int k, n, m, q;
cin >> k >> n >> m >> q;
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
while (q--){
int u, v;
cin >> u >> v;
for(int i = u; i <= v; i++){
for(auto node: g[i]){
dis[node.first] = min(dis[node.first], dis[i] + node.second);
}
}dijkstra(u);
if(dis[v] == inf){
cout << -1 << endl;
}else {
cout << dis[v] << endl;
}
}
}
