#include <bits/stdc++.h>
using namespace std;
using INT = long long;
using pii = pair<INT, INT>;
const int NN = 600030, M = 21;
int dep[NN], p[NN][M], rt[NN];
vector<INT> tadj[NN];
vector<pii> adj[NN];
INT dst[NN], val[NN];
void dfs(int u, int pa = 0) {
  p[u][0] = pa;
  dep[u] = dep[pa] + 1;
  for (int i = 1; i < M; i++) p[u][i] = p[p[u][i - 1]][i - 1];
  for (int v : tadj[u]) dfs(v, u);
}
int k_th(int u, int k) {
  while (k) {
    u = p[u][__builtin_ctz(k)];
    k ^= k & -k;
  }
  return u;
}
int lca(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  v = k_th(v, dep[v] - dep[u]);
  if (u == v) return u;
  for (int t = M; t--;) {
    if (p[u][t] != p[v][t]) u = p[u][t], v = p[u][t];
  }
  return p[u][0];
}
int find(int u) { return rt[u] == u ? u : rt[u] = find(rt[u]); }
int main() {
  int n, m, K, Q, u, v, w;
  cin >> n >> m >> K >> Q;
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  memset(dst, 0x3f, sizeof dst);
  set<pair<INT, int>> st;
  for (int i = 1; i <= K; i++) st.insert({dst[i] = 0, i}), rt[i] = i;
  for (int i = K + 1; i <= n; i++) st.insert({dst[i], i});
  for (int i = 1; i <= n; i++) {
    int u = st.begin()->second;
    st.erase(st.begin());
    for (auto t : adj[u]) {
      if (dst[t.first] > dst[u] + t.second) {
        st.erase({dst[t.first], t.first});
        rt[t.first] = rt[u];
        st.insert({dst[t.first] = dst[u] + t.second, t.first});
      }
    }
  }
  vector<pair<INT, pii>> edge;
  for (int i = 1; i <= n; i++) {
    for (auto t : adj[i])
      if (i > t.first) {
        int u = rt[i], v = rt[t.first];
        if (u == v) continue;
        edge.emplace_back(dst[i] + dst[t.first] + t.second, pii(u, v));
      }
  }
  sort(edge.begin(), edge.end());
  int N = K;
  for (auto t : edge) {
    int u = find(t.second.first), v = find(t.second.second);
    if (u == v) continue;
    ++N;
    tadj[N].push_back(u);
    tadj[N].push_back(v);
    rt[u] = rt[v] = rt[N] = N;
    val[N] = t.first;
  }
  dfs(N);
  while (Q--) {
    scanf("%d%d", &u, &v);
    printf("%I64d\n", val[lca(u, v)]);
  }
  return 0;
}
