#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
const long long MOD = 1000000007;
const long long INF = 2000000000;
const long long DESPACITO = 1000000000000000000;
namespace minmax {
template <class T>
T max(T&& A) {
  return A;
}
template <class T>
T min(T&& A) {
  return A;
}
template <class T>
T max(T&& A, T&& B) {
  return A > B ? A : B;
}
template <class T>
T chmin2(T&& A, T&& B) {
  return A < B ? A : B;
}
template <class T, class... Ts>
T max(T&& A, Ts&&... ts) {
  T B = max(ts...);
  return A > B ? A : B;
}
template <class T, class... Ts>
T min(T&& A, Ts&&... ts) {
  T B = min(ts...);
  return A < B ? A : B;
}
template <class T, class... Ts>
T chmax(T&& A, Ts&&... ts) {
  A = max(A, ts...);
  return A;
}
template <class T, class... Ts>
T chmin(T&& A, Ts&&... ts) {
  A = min(A, ts...);
  return A;
}
template <class T1, class T2>
void chmin2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B < A) A = B, Aa = Bb;
}
template <class T1, class T2>
void chmax2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B > A) A = B, Aa = Bb;
}
}  // namespace minmax
namespace input {
template <class T>
void re(T&& Xx) {
  cin >> Xx;
}
template <class T1, class T2>
void re(pair<T1, T2>& Pp) {
  re(Pp.first);
  re(Pp.second);
}
template <class T>
void re(vector<T>& Aa) {
  for (long long i = 0; i < (long long)(Aa).size(); i++) re(Aa[i]);
}
template <class T1, class T2>
void rea(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea(T1&& Aa, T2 t, Ts&&... ts) {
  rea(Aa, t);
  rea(ts...);
}
template <class T1, class T2>
void rea1(T1&& Aa, T2 t) {
  for (long long i = 1; i <= t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea1(T1&& Aa, T2 t, Ts&... ts) {
  rea1(Aa, t);
  rea1(ts...);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int32_t Xx) { cout << Xx; }
void pr(bool Xx) { cout << Xx; }
void pr(long long Xx) { cout << Xx; }
void pr(long long unsigned Xx) { cout << Xx; }
void pr(double Xx) { cout << Xx; }
void pr(char Xx) { cout << Xx; }
void pr(const string& Xx) { cout << Xx; }
void pr(const char* Xx) { cout << Xx; }
void pr(const char* Xx, size_t len) { cout << string(Xx, len); }
void ps() { cout << "\n"; }
void pn() {}
void pw() { pr(" "); }
void pc() {
  pr("]");
  ps();
}
template <class T1, class T2>
void pr(const pair<T1, T2>& Xx) {
  pr(Xx.first);
  pw();
  pr(Xx.second);
}
template <class T>
void pr(const T&);
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
bool parsepair(const pair<T1, T2>& Xx) {
  return true;
}
template <class T>
bool parsepair(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) pr(Aa[i]), pw();
  ps();
}
template <class T1, class T2>
void pna(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) pr(Aa[i]), ps();
}
template <class T1, class T2>
void psa2(T1&& Aa, T2 t1, T2 t2) {
  for (long long i = 0; i < t1; i++) {
    for (long long j = 0; j < t2; j++) pr(Aa[i][j]), pw();
    ps();
  }
}
template <class T>
void pr(const T& Xx) {
  if (!(long long)(Xx).size()) return;
  bool fst = 1;
  bool op = 0;
  if (parsepair(*Xx.begin())) op = 1;
  for (const auto& Aa : Xx) {
    if (!fst) pw();
    if (op) pr("{");
    pr(Aa), fst = 0;
    if (op) pr("}");
  }
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pw();
  }
  ps(ts...);
}
template <class T>
void pn(const T& t) {
  for (const auto& Aa : t) ps(Aa);
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pw();
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  bool op = 0;
  if (parsepair(t)) op = 1;
  if (op) pr("{");
  pr(t);
  if (op) pr("}");
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& Xx, const T2& y) {
  pr("[", y, "] = ");
  ps(Xx);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, Xx, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, Xx, y, rest...);
}
template <class T>
void __fn(long long n, const char* name, const T& Xx) {
  for (long long i = 0; i < n; i++) pr(name), __f(name, Xx[i], i);
}
}  // namespace trace
}  // namespace output
using namespace minmax;
using namespace input;
using namespace output;
using namespace output::trace;
const long long N = 3e5 + 5;
long long n, m, k, Q, d[N], ans[N], p[N];
vector<pii> g[N], queries[N];
vector<pair<long long, pii>> oldedges, edges;
const long long NN = 3e5 + 5;
namespace DSU {
long long nn, par[NN], size_[NN];
void build(long long Q) {
  nn = Q;
  for (long long i = 0; i < nn; i++) {
    par[i] = i;
    size_[i] = 1;
  }
}
long long getpar(long long x) {
  long long pp = x;
  while (par[pp] != pp) pp = par[pp];
  while (par[x] != x) {
    long long z = par[x];
    par[x] = pp;
    x = z;
  }
  return pp;
}
void merge(long long x, long long y, long long w) {
  x = getpar(x);
  y = getpar(y);
  if (x == y) return;
  if (size_[x] < size_[y]) swap(x, y);
  for (auto& u : queries[y]) {
    if (getpar(u.first) == x)
      ans[u.second] = w;
    else
      queries[x].emplace_back(u);
  }
  queries[y].clear();
  par[y] = x, size_[x] += size_[y];
}
}  // namespace DSU
using namespace DSU;
void makeG() {
  for (long long i = 0; i < m; i++) {
    long long u, v, w;
    re(u, v, w);
    u--, v--;
    oldedges.emplace_back(w, make_pair(u, v));
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
}
void dijkstra() {
  long long i;
  set<pii> q;
  for (i = 0; i < n; i++) d[i] = INF, p[i] = i;
  for (i = 0; i < k; i++) d[i] = 0, q.insert({0, i}), p[i] = i;
  while (!q.empty()) {
    auto [y, v] = *q.begin();
    q.erase(q.begin());
    for (auto& [to, w] : g[v]) {
      if (d[to] > d[v] + w) {
        q.erase({d[to], to});
        d[to] = d[v] + w;
        q.insert({d[to], to});
        p[to] = v;
      }
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long i;
  re(n, m, k, Q);
  makeG();
  dijkstra();
  for (auto& [w, ed] : oldedges)
    if (p[ed.first] != p[ed.second])
      edges.emplace_back(w + d[ed.first] + d[ed.second],
                         make_pair(p[ed.first], p[ed.second]));
  sort(edges.begin(), edges.end());
  for (i = 0; i < Q; i++) {
    long long u, v;
    re(u, v);
    --u;
    --v;
    queries[u].emplace_back(v, i);
    queries[v].emplace_back(u, i);
  }
  build(n);
  for (auto& [w, ed] : edges) merge(ed.first, ed.second, w);
  for (i = 0; i < Q; i++) ps(ans[i]);
  return 0;
}
