#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
const int N = 5e5+5, Q = 1e6+5;
const int K = 6, inf = 1e15+1;
struct Query{
int a,b,id;
Query(int a = 0, int b = 0, int id = 0): a(a), b(b), id(id) {}
};
int n, m, q, k;
int answer[N], d[11][N];
vector<pair<int,int>> adj[N], r_adj[N];
void Dnc(int l, int r, vector<Query>& Q){
if(l == r){
for(Query cur_q : Q){
answer[cur_q.id] = 0;
}
return;
}
int m = l+r>>1;
for(int i = l; i <= r; i++){
for(int j = 0; j < 2*k; j++){
d[j][i] = inf;
}
}
for(int id = 0, i = max(l, m-k*2+1); i <= m; i++, id++){
for(pair<int,int> e : adj[i]){
int v = e.fi, w = e.se;
if(v > m){
d[id][i] = 0;
ckmn(d[id][v], w);
}
}
}
for(int i = m; i >= l; i--){
for(pair<int,int> e : r_adj[i]){
int v = e.fi, w = e.se;
for(int j = 0; j < 2*k; j++){
ckmn(d[j][v], d[j][i] + w);
}
}
}
for(int i = m+1; i <= r; i++){
for(pair<int,int> e : adj[i]){
int v = e.fi, w = e.se;
for(int j = 0; j < 2*k; j++){
ckmn(d[j][v], d[j][i] + w);
}
}
}
vector<Query> Qleft, Qright;
for(Query cur_q : Q){
int l = cur_q.a, r = cur_q.b;
if(l <= m && r > m){
for(int i = 0; i < 2*k; i++){
ckmn(answer[cur_q.id], d[i][l] + d[i][r]);
}
}
else{
if(r <= m){
Qleft.pb(cur_q);
}
else Qright.pb(cur_q);
}
}
Dnc(l, m, Qleft);
Dnc(m+1, r, Qright);
return;
}
void solve()
{
cin >> k >> n >> m >> q;
for(int i = 1; i <= m; i++){
int a,b,t; cin >> a >> b >> t;
adj[a].pb(make_pair(b, t));
r_adj[b].pb(make_pair(a, t));
}
vector<Query> Q;
for(int i = 1; i <= q; i++){
int a,b; cin >> a >> b;
Q.pb(Query(a, b, i));
answer[i] = inf;
}
Dnc(0, n, Q);
for(int i = 1; i <= q; i++){
cout << (answer[i] == inf ? -1 : answer[i]) <<"\n";
} cout <<"\n";
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
solve();
return 0;
}
