// #pragma gcc optimize("Ofast")
// #pragma GCC optimization("Ofast")
// #pragma optimize(Ofast)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
/**
* author: tpa1410 - futorankusu
* rose, hanni, minji
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
#define rose() ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define mset(a) memset(a, 0, sizeof(a))
#define endl '\n'
const ll hanni = 1e4, minji = 1e9;
struct Matrix{
long long int a[5][5];
Matrix(){
for(int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
a[i][j] = minji;
}
}
}
};
Matrix mul(Matrix a, Matrix b){
Matrix c;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
c.a[i][j] = minji;
for (int k = 0; k < 5; k++) {
c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
}
}
}
return c;
}
Matrix up[50005][18];
signed main(){
int k, n, m, o;
cin >> k >> n >> m >> o;
for(int i=1; i<=m; i++) {
int u, v, w;
cin >> u >> v >> w;
// up[j][i]: tầng thứ 2^i bên cạnh tầng j
up[u/k][0].a[u%k][v%k] = w;
// a[x][y]: x là vị trí của đỉnh u trong tầng u nằm, y tương tự là của v
}
for(int i=1; (1 << i) <= n; i++){
for(int j=0; j + (1 << i) - 1 <= n; j++){
up[j][i] = mul(up[j][i-1], up[j+(1<<(i-1))][i-1]);
}
}
for(int i = 0; i<o; i++){
int a, b;
cin >> a >> b;
Matrix res;
for(int j = 0; j < 5; j++){
res.a[j][j] = 0;
}
if(a == b){
cout << 0 << endl;
continue;
}
int div1 = a / k, div2 = b / k;
int dist = div2 - div1;
for(int j = 16; j >= 0; j--){
if(dist & (1 << j)){
res = mul(res, up[div1][j]);
div1 += (1 << j);
}
}
if(res.a[a % k][b % k] == minji) cout << -1 << endl;
else cout << res.a[a % k][b % k] << endl;
}
}
