#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 5e4 + 1;
int dist[nmax][41][5];
int k;
int get(int a, int b){
int A = a / k;
int B = b / k;
if(A >= B){
return -1;
}
vector <pii> vec;
vec.pb({a, 0});
while(B > A + 40){
vector <pii> nw;
int d[5];
fill(d, d + 5, 1e9 + 1);
for(auto x : vec){
int v = x.f, D = x.s;
for(int j = 0; j < k; j++){
d[j] = min(d[j], dist[v][40][j] + D);
}
}
A += 40;
vec.clear();
for(int j = 0; j < k; j++){
if(d[j] != 1e9 + 1)
vec.pb({A * k + j, d[j]});
}
}
int ans = 1e9 + 1;
for(auto x : vec){
int v = x.f, D = x.s;
ans = min(ans, dist[v][B - A][b % k] + D);
}
if(ans == 1e9 + 1) return -1;
return ans;
}
int main(){
int n, m, o; cin >> k >> n >> m >> o;
vector <vector <pii> > g(n + 1);
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
int t; cin >> t;
g[u].pb({v, t});
}
for(int i = n - 1; i >= 0; i--){
for(int j = 0; j <= 40; j++){
for(int x = 0; x < k; x++)
dist[i][j][x] = 1e9 + 1;
}
for(auto ed : g[i]){
int to = ed.f, x = ed.s;
dist[i][1][to % k] = x;
}
for(int j = 2; j <= 40; j++){
for(int x = 0; x < k; x++){
for(auto ed : g[i]){
int to = ed.f;
dist[i][j][x] = min(dist[i][j][x], dist[to][j - 1][x] + dist[i][1][to % k]);
}
}
}
}
while(o--){
int a, b; cin >> a >> b;
cout << get(a, b) << "\n";
}
return 0;
}
