#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 * 100 + 5;
long long n, m, k, q, par[maxn], dis[maxn], root[maxn], ans[maxn];
vector<pair<long long, long long>> adj[maxn], g[maxn];
vector<pair<long long, long long>> qr[maxn];
set<pair<long long, long long>> s;
pair<pair<long long, long long>, long long> e[maxn];
vector<pair<long long, pair<long long, long long>>> Eg;
vector<long long> mo[maxn];
long long getroot(long long v) {
  return root[v] == v ? v : root[v] = getroot(root[v]);
}
void merge(long long u, long long v, long long w) {
  if (mo[u].size() < mo[v].size()) swap(u, v);
  int i = 0;
  while (mo[v].size()) {
    i = mo[v].size() - 1;
    mo[u].push_back(mo[v][i]);
    long long x = mo[v][i];
    for (int j = 0; j < qr[x].size(); j++) {
      long long y = qr[x][j].first, id = qr[x][j].second;
      if (getroot(y) == u) {
        ans[id] = w;
      }
    }
    mo[v].pop_back();
  }
  root[v] = u;
}
void initialize() {
  for (int i = 1; i <= n; i++) {
    root[i] = i;
    mo[i].push_back(i);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m >> k >> q;
  for (int i = 1; i <= m; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    e[i] = {{u, v}, w};
  }
  for (int i = 1; i <= q; i++) {
    long long a, b;
    cin >> a >> b;
    qr[a].push_back({b, i});
    qr[b].push_back({a, i});
  }
  memset(dis, 63, sizeof dis);
  for (int i = 1; i <= k; i++) {
    par[i] = i;
    dis[i] = 0;
    s.insert({0, i});
  }
  while (s.size()) {
    auto k = s.begin();
    long long v = k->second;
    s.erase(*k);
    for (auto u : adj[v]) {
      if (dis[u.first] > dis[v] + u.second) {
        s.erase({dis[u.first], u.first});
        dis[u.first] = dis[v] + u.second;
        s.insert({dis[u.first], u.first});
        par[u.first] = par[v];
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    long long u = e[i].first.first, v = e[i].first.second, w = e[i].second;
    if (par[u] != par[v]) {
      w = dis[v] + dis[u] + w;
      u = par[u];
      v = par[v];
      g[u].push_back({v, w});
      g[v].push_back({u, w});
      Eg.push_back({w, {u, v}});
    }
  }
  initialize();
  sort(Eg.begin(), Eg.end());
  for (int i = 0; i < Eg.size(); i++) {
    long long u = Eg[i].second.first, v = Eg[i].second.second;
    if (getroot(u) != getroot(v)) {
      merge(u, v, Eg[i].first);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << endl;
  }
}
