#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
const int Inf = 0x3f3f3f3f;
vector<pair<int, int>> Adj[N], Order, Order2[N];
int n, m, k, o, C[N], D[N], mark[N], ans[N];
void Dijkstra(int v)
{
memset(D, 63, sizeof D);
memset(mark, 0, sizeof mark);
D[v] = 0;
priority_queue<pair<int, int>> PQ;
PQ.emplace(0, v);
while (!PQ.empty())
{
int v = PQ.top().second; PQ.pop();
if (mark[v]) continue;
mark[v] = true;
for (auto [u, w] : Adj[v])
if (D[u] > D[v] + w)
D[u] = D[v] + w, PQ.emplace(-D[u], u);
}
}
void DFS(int v, int comp)
{
mark[v] = true;
C[v] = comp;
for (auto [u, w] : Adj[v])
D[u] = D[v] + w, DFS(u, comp);
}
void Subtask1()
{
for (int i = 0; i < n; i++)
if (!mark[i]) DFS(i, i);
for (auto [u, v] : Order)
{
if (u < v) swap(u, v);
if (C[u] == C[v])
printf("%d\n", D[u] - D[v]);
else
printf("%d\n", -1);
}
}
signed main()
{
scanf("%d%d%d%d", &k, &n, &m, &o);
for (int i = 0; i < m; i++)
{
int a, b, t;
scanf("%d%d%d", &a, &b, &t);
Adj[a].emplace_back(b, t);
}
vector<int> V;
for (int i = 0; i < o; i++)
{
int a, b;
scanf("%d%d", &a, &b);
Order.emplace_back(a, b);
Order2[a].emplace_back(b, i);
V.push_back(a);
}
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
if (k == 1) {Subtask1(); return 0;}
for (int x : V)
{
Dijkstra(x);
for (auto [u, i] : Order2[x])
ans[i] = D[u];
}
for (int i = 0; i < o; i++)
printf("%d\n", (ans[i] == Inf ? -1 : ans[i]));
return 0;
}
