#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
const int MAXN = 5*1e4+5, MAX = 15, INF = 1e9;
vector<int> adj[MAXN], w[MAXN];
int mn[MAX+5][5][MAXN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int k,n,m,q; cin>>k>>n>>m>>q;
for(int i = 0; i <= MAX; i++)
for(int md = 0; md < k; md++)
for(int j = 0; j < n; j++)mn[i][md][j] = INF;
for(int i = 0; i < m; i++){
int a,b,c; cin>>a>>b>>c;
adj[a].push_back(b); w[a].push_back(c);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < sz(adj[i]); j++){
int viz = adj[i][j];
mn[0][viz%k][i] = min( mn[0][viz%k][i], w[i][j] );
}
}
for(int i = 1; i <= MAX; i++)
for(int md = 0; md < k; md++)
for(int j = 0; j < n; j++){
for(int md2 = 0; md2 < k; md2++){
mn[i][md][j] = min( mn[i][md][j], mn[i-1][md2][j] + mn[i-1][md][ j + (1<<(i-1))*k + md2 ] );
}
}
while(q--){
int a,b; cin>>a>>b;
int qtd = b/k-a/k;
int cur[5]; for(int md = 0; md < k; md++)cur[md] = INF; cur[a%k] = 0;
a = (a/k)*k;
for(int i = MAX; i >= 0; i--)
if(qtd & (1<<i)){
int nxt[5]; for(int md = 0; md < k; md++)nxt[md] = INF;
for(int md = 0; md < k; md++)
for(int md2 = 0; md2 < k; md2++){
nxt[md] = min(nxt[md], cur[md2] + mn[i][md][ a+ md2] );
}
a += (1<<i);
for(int md = 0; md < k; md++)cur[md] = nxt[md];
}
if(cur[b%k] == INF)cout<<"-1\n";
else cout<<cur[b%k]<<"\n";
}
}
