#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
inline long long input() {
  long long n;
  cin >> n;
  return n;
}
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const long long INF = 8e18;
long long n, m, k, q;
long long ans[MAXN];
bool mark[MAXN];
long long dis[MAXN];
long long par[MAXN];
vector<long long> adj[MAXN];
vector<long long> w[MAXN];
vector<pair<long long, pair<long long, long long> > > edges2;
long long pr[MAXN];
long long sz[MAXN];
vector<long long> comp[MAXN];
bool ismark[MAXN];
set<pair<long long, long long> > st;
vector<pair<pair<long long, long long>, long long> > edges;
vector<pair<long long, long long> > que[MAXN];
long long getroot(long long v) {
  if (pr[v] == v) {
    return v;
  } else {
    pr[v] = getroot(pr[v]);
    return pr[v];
  }
}
bool merge(long long v, long long u) {
  long long vp = getroot(v), up = getroot(u);
  if (vp == up) {
    return false;
  }
  if (sz[vp] > sz[up]) {
    swap(vp, up);
  }
  pr[vp] = up;
  sz[up] += sz[vp];
  return true;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m >> k >> q;
  for (int i = 1; i <= n; i++) {
    dis[i] = INF;
  }
  for (int i = 1; i <= k; i++) {
    ismark[i] = true;
    dis[i] = 0;
    par[i] = i;
    pr[i] = i;
    comp[i].push_back(i);
    st.insert({0, i});
  }
  long long a, b, wei;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> wei;
    adj[a].push_back(b);
    adj[b].push_back(a);
    w[a].push_back(wei);
    w[b].push_back(wei);
    edges.push_back({{a, b}, wei});
  }
  while (!st.empty()) {
    auto it = st.begin();
    st.erase(it);
    long long v = it->second;
    if (it->first != dis[v]) continue;
    mark[v] = true;
    for (int i = 0; i < adj[v].size(); i++) {
      long long u = adj[v][i];
      if (mark[u]) continue;
      long long cnt = dis[u];
      dis[u] = min(dis[u], dis[v] + w[v][i]);
      if (dis[u] == dis[v] + w[v][i] and dis[u] != cnt) par[u] = par[v];
      st.insert({dis[u], u});
    }
  }
  for (int i = 0; i < edges.size(); i++) {
    a = edges[i].first.first;
    b = edges[i].first.second;
    long long ap = par[a];
    long long bp = par[b];
    if (ap != bp) {
      wei = dis[a] + edges[i].second + dis[b];
      edges2.push_back({wei, {ap, bp}});
    }
  }
  sort((edges2).begin(), (edges2).end());
  for (int i = 0; i < q; i++) {
    cin >> a >> b;
    que[a].push_back({b, i});
    que[b].push_back({a, i});
    ans[i] = INF;
  }
  long long tmp;
  for (int i = 0; i < edges2.size(); i++) {
    a = edges2[i].second.first;
    b = edges2[i].second.second;
    if (merge(a, b)) {
      if (sz[a] > sz[b]) {
        swap(a, b);
      }
      for (auto u : comp[a]) {
        for (auto j : que[u]) {
          tmp = j.first;
          if (getroot(u) == getroot(tmp)) {
            ans[j.second] = min(ans[j.second], edges2[i].first);
          }
        }
        comp[b].push_back(u);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << "\n";
  }
}
