#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
struct Edge {
int x, y, t;
Edge(int xi, int yi, int ti):x(xi),y(yi),t(ti){}
};
int k, n, m, q, x, y, t;
vector<vector<Edge>> graph;
signed main() {
cin >> k >> n >> m >> q;
if(k == 1) {
vector<int> a(n, 1e10), prefix(n);
for(int i = 0; i < m; i++) {
cin >> x >> y >> t;
a[x] = t;
}
for(int i = 0; i < n; i++) prefix[i] = a[i] + (i == 0 ? 0 : prefix[i - 1]);
while(q--) {
cin >> x >> y;
if(prefix[y - 1] - (x == 0 ? 0 : prefix[x - 1]) >= 1e10) cout << "-1\n";
else cout << (prefix[y - 1] - (x == 0 ? 0 : prefix[x - 1])) << "\n";
}
return 0;
}
graph = vector<vector<Edge>>(n);
for(int i = 0; i < m; i++) {
cin >> x >> y >> t;
graph[x].push_back(Edge(x, y, t));
}
priority_queue<pair<int,int>> pq;
vector<int> dist(n, LLONG_MAX);
pair<int,int> temp;
pq.push({0, 0});
while(pq.size()) {
temp = pq.top();
pq.pop();
temp.ff = -temp.ff;
//cout << temp.ff << " " << temp.ss << "\n";
if(dist[temp.ss] < temp.ff) continue;
dist[temp.ss] = temp.ff;
for(auto j : graph[temp.ss]) {
if(temp.ff + j.t < dist[j.y]) pq.push({-(temp.ff + j.t), j.y});
}
}
while(q--) {
cin >> x >> y;
if(dist[y] == LLONG_MAX) cout << "-1\n";
else cout << dist[y] << "\n";
}
}
