#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);
int k, n, ed, q, a, b, c;
vector<pii> v[50005];
vector<pii> rev[50005];
vector<int> br[50005];
map<int, int> m[50005];
map<int, int> bio[50005];
void rek(int l, int r) {
if (l >= r) return;
int mid = (l+r)/2;
for (int i = mid-1; i >= l; i--) {
for (int j = 0; j < br[mid].size(); j++) {
int poc = br[mid][j];
for (int w = 0; w < br[i+1].size(); w++) {
int cvor = br[i+1][w];
if (m[cvor][poc] == 0 && cvor != poc) continue;
for (int slj = 0; slj < rev[cvor].size(); slj++) {
int sus = rev[cvor][slj].X;
int dist = m[cvor][poc]+rev[cvor][slj].Y;
if (m[sus][poc] == 0 || m[sus][poc] > dist) m[sus][poc] = dist;
}
}
}
}
for (int i = mid+2; i <= r; i++) {
for (int j = 0; j < br[mid+1].size(); j++) {
int poc = br[mid+1][j];
for (int w = 0; w < br[i-1].size(); w++) {
int cvor = br[i-1][w];
if (m[poc][cvor] == 0 && cvor != poc) continue;
for (int slj = 0; slj < v[cvor].size(); slj++) {
int sus = v[cvor][slj].X;
int dist = m[poc][cvor]+v[cvor][slj].Y;
if (m[poc][sus] == 0 || m[poc][sus] > dist) m[poc][sus] = dist;
}
}
}
}
rek(l, mid);
rek(mid+1, r);
}
int trazimid(int l, int r, int lo, int hi) {
if (hi < l || r < lo) return -1;
int mid = (lo+hi)/2;
if (l <= mid && mid <= r) return mid;
return max(trazimid(l, r, lo, mid), trazimid(l, r, mid+1, hi));
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> k >> n >> ed >> q;
for (int i = 0; i < ed; i++) {
cin >> a >> b >> c;
v[a].push_back({b, c});
rev[b].push_back({a, c});
}
for (int i = 0; i < n; i++) br[i/k].push_back(i);
rek(0, (n-1)/k);
for (int i = 0; i < q; i++) {
cin >> a >> b;
int sred = trazimid(a/k, b/k, 0, (n-1)/k);
if (sred == b/k) {
if (m[a][b] == 0) cout << "-1\n";
else cout << m[a][b] << "\n";
}
else {
int mini = 1e9;
for (int j = 0; j < br[sred].size(); j++) {
int cvor1 = br[sred][j];
for (int w = 0; w < v[cvor1].size(); w++) {
int cvor2 = v[cvor1][w].X;
int tez = v[cvor1][w].Y;
if (m[a][cvor1] == 0 && a != cvor1) continue;
if (m[cvor2][b] == 0 && b != cvor2) continue;
mini = min(mini, m[a][cvor1]+tez+m[cvor2][b]);
}
}
if (mini == 1e9) cout << "-1\n";
else cout << mini << "\n";
}
}
return 0;
}
