#include<bits/stdc++.h>
using namespace std;
const int maxN = 1e5+1;
const int lg = 17;
const int inf_set = 0x3f;
const int inf_comp = 0x3f3f3f3f;
int k;
vector<pair<int,int>> graph[maxN];
int dp[maxN][5][lg][5];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t, n, m, a, b, c, d;
cin >> k >> n >> m >> t;
memset(dp, inf_set, sizeof(dp));
// EDGES
for(int i = 0; i < m; ++i){
cin >> a >> b >> d;
graph[a].push_back({b,d});
dp[a/k][a%k][0][b%k] = d;
}
// EXPLORING THE GRAPH
for(int i = 1; i < lg; ++i){
for(int deepness = 0; deepness + (1<<i) < (n + k -1)/k; ++deepness){
for(int ini = 0; ini < k; ++ini){
for(int mid = 0; mid < k; ++mid){
for(int fin = 0; fin < k; ++fin){
dp[deepness][ini][i][fin] = min(dp[deepness][ini][i][fin], dp[deepness][ini][i-1][mid] + dp[deepness + (1<<(i-1))][mid][i-1][fin]);
}
}
}
}
}
// QUERIES
int queries[k][k]; // New layer, Mod
int temp[k][k];
while(t--){
cin >> a >> b;
if(a/k >= b/k) cout << -1 << '\n';
else{
memset(queries, inf_set, sizeof(queries));
for(int i = 0; i < k; ++i) queries[i][i] = 0;
c = a/k;
d = (b/k) - (a/k); // distance from one to another
//cout << d << '\n';
for(int i = lg-1; i >= 0; --i){
if(d&(1<<i)){
//cout << i << '\n';
memset(temp, inf_set, sizeof(temp));
for(int ori = 0; ori < k; ++ori){
for(int dest = 0; dest < k; ++dest){
for(int mid = 0; mid < k; ++mid){
temp[ori][dest] = min(temp[ori][dest], queries[ori][mid] + dp[c][mid][i][dest]);
}
}
}
memcpy(queries, temp, sizeof(temp));
c += (1<<i);
}
}
if(queries[a%k][b%k] != inf_comp) cout << queries[a%k][b%k] << '\n';
else cout << -1 << '\n';
}
}
return 0;
}
