#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define read_input(file) if (fopen(file".inp", "r")) freopen(file".inp", "r", stdin);
#define file(file) freopen (file".inp", "r", stdin); freopen (file".out", "w", stdout);
const int N = 5e4, inf = 1e12;
int n, m, o, k;
struct matrix{
vector <vector<int>> d;
void init(int n, int m, int v){
d.resize(n, vector<int>(m, v));
}
};
matrix operator* (const matrix &a, const matrix &b){
matrix c;
c.init(a.d.size(), b.d[0].size(), inf);
for (int i = 0; i < (int)a.d.size(); ++i)
for (int j = 0; j < (int)b.d[0].size(); ++j)
for (int k = 0; k < (int)a.d[0].size(); ++k)
c.d[i][j] = min(c.d[i][j], a.d[i][k] + b.d[k][j]);
return c;
}
matrix M[N + 5];
matrix binlift[N + 5][17];
void solve(){
cin >> k >> n >> m >> o;
int sum = n / k;
for (int i = 0; i <= sum; ++i)
M[i].init(k, k, inf);
for (int i = 1; i <= m; ++i){
int u, v, w;
cin >> u >> v >> w;
M[u / k].d[u % k][v % k] = w;
}
for (int i = 0; i <= sum; ++i) binlift[i][0] = M[i];
for (int i = 1; i <= 16; ++i)
for (int j = 0; j <= sum - (1 << i); ++j)
binlift[j][i] = binlift[j][i - 1] * binlift[j + (1 << (i - 1))][i - 1];
while (o--){
int u, v;
cin >> u >> v;
if (u > v){
cout << "-1\n";
continue;
}
matrix nw;
nw.init(k, k, inf);
nw.d[0][u % k] = 0;
int s = u / k, t = v / k;
for (int i = 16; i >= 0; --i)
if (s + (1 << i) <= t){
nw = nw * binlift[s][i];
s += (1 << i);
}
cout << (nw.d[0][v % k] >= inf ? -1 : nw.d[0][v % k]) << "\n";
}
}
signed main(){
faster;
// file("file");
// read_input("file");
int tt = 1;
// cin >> tt;
while (tt--){
solve();
}
}
