#include <bits/stdc++.h>
using namespace std;
#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int t;cin >> t;while (t--) solve();
#define rf(__abc__) freopen(__abc__".inp","r",stdin);freopen(__abc__".out","w",stdout);
const int mod = 1e9 + 7;
long long pw(long long x,long long y) {
if (y == 0) return 1;
if (y % 2 == 0) {
long long a = pw(x,y/2);
return a*a%mod;
} else {
long long a = pw(x,y - 1);
return a*x%mod;
}
}
int add(int x,int y) {
x += y;
if (x >= mod) x -= mod;
return x;
}
int subtract(int x,int y) {
x -= y;
if (x < 0) x += mod;
return x;
}
int mul(long long x,int y) {
x *= y;
if (x >= mod) x %= mod;
return x;
}
///Code goes here
struct matrix {
long long data[5][5];
int row,col;
matrix () {
}
matrix (int r,int c) {
row = r,col = c;
for (int i = 0;i < row;i++) for (int j = 0;j < col;j++) data[i][j] = 0;
}
matrix operator * (const matrix & b) {
matrix a = *this;
matrix c(a.row,b.col);
for (int i = 0;i < a.row;i++) {
for (int j = 0;j < b.col;j++) {
c.data[i][j] = mod;
for (int k = 0;k < a.col;k++) {
c.data[i][j] = min(c.data[i][j],a.data[i][k] + b.data[k][j]);
}
}
}
return c;
}
};
matrix mat[50009];
//order:left -> right
int k,n,m,q;
vector <pair<int,int>> adj[50009];
struct query {
int l,r,index;
} ask[10009];
matrix answer[10009];
matrix acc[50009];
void dnc(int l,int r,vector <query> & bruh) {
if (l == r) {
for (auto x : bruh) {
answer[x.index] = mat[l];
}
return;
}
int mid = (l + r) >> 1;
acc[mid] = mat[mid];
acc[mid + 1] = mat[mid + 1];
for (int i = mid - 1;i >= l;i--) {
acc[i] = mat[i] * acc[i + 1];
}
for (int i = mid + 2;i <= r;i++) {
acc[i] = acc[i - 1] * mat[i];
}
vector <query> left,right;
for (auto x : bruh) {
if (x.l > mid) right.push_back(x);
else if (x.r <= mid) left.push_back(x);
else answer[x.index] = acc[x.l] * acc[x.r];
}
dnc(l,mid,left);
left.clear();
dnc(mid + 1,r,right);
right.clear();
}
int main() {
//rf("");
FastIO
//MULTEST
cin >> k >> n >> m >> q;
n = (n + k - 1)/k*k;
for (int i = 1;i <= m;i++) {
int u,v,w;cin >> u >> v >> w;
adj[v].push_back({u,w});
}
for (int i = 0;i * k <= n;i++) {
//i*k,i*k + 1,...,i*k + k - 1
///init
for (int d = 0;d < k;d++) {
for (int b = 0;b < k;b++) {
mat[i].data[d][b] = 0;
}
}
mat[i].row = mat[i].col = k;
///create min-plus matrix
for (int node = i*k;node <= i*k + k - 1;node++) {
for (auto c : adj[node]) {
int child = c.first,cost = c.second;
mat[i].data[child%k][node%k] = cost;
}
}
///fill in missing value
for (int d = 0;d < k;d++) {
for (int b = 0;b < k;b++) {
if (!mat[i].data[d][b]) mat[i].data[d][b] = mod;
}
}
}
vector <query> allquery;
for (int i = 1;i <= q;i++) {
int l,r;cin >> l >> r;
ask[i] = {l,r,i};
if (l/k != r/k) allquery.push_back({l/k + 1,r/k,i});
}
dnc(1,n,allquery);
for (int i = 1;i <= q;i++) {
if (ask[i].l/k == ask[i].r/k) cout << -1 << '\n';
else cout << (answer[i].data[ask[i].l%k][ask[i].r%k] >= 1e9 ? -1 : answer[i].data[ask[i].l%k][ask[i].r%k]) << '\n';
}
return 0;
}
