#include <bits/stdc++.h>
using namespace std;
inline void In(long long _, ...) {
  va_list lis;
  va_start(lis, _);
  while (_--) scanf("%lld", va_arg(lis, long long *));
}
inline void Out(long long _, ...) {
  va_list lis;
  va_start(lis, _);
  while (_--) printf("%lld\n", va_arg(lis, long long));
}
inline void Out_(long long _, ...) {
  va_list lis;
  va_start(lis, _);
  while (_--) printf("%lld ", va_arg(lis, long long));
}
const int N = 6E5 + 10;
long long n, m, k, t, tot;
long long fa[N], head[N], vis[N], dis[N], f[N][24], p[N][24], dep[N];
struct Node {
  long long u, d;
  bool operator<(const Node &tmp) const { return d > tmp.d; }
};
struct Edge {
  long long frm, nxt, to, w;
  bool operator<(const Edge &tmp) const { return w < tmp.w; }
} e[N];
priority_queue<Node> q;
inline void add_edge(long long u, long long v, long long w, int flag) {
  e[++tot].nxt = head[u];
  e[tot].frm = u;
  e[tot].to = v;
  e[tot].w = w;
  head[u] = tot;
  if (flag) add_edge(v, u, w, 0);
}
void Dij() {
  for (int(i) = (1); (i) <= (n); ++(i)) {
    if (i > k)
      dis[i] = LONG_LONG_MAX >> 1;
    else
      q.push((Node){i, 0});
  }
  while (!q.empty()) {
    Node cur = q.top();
    q.pop();
    long long u = cur.u;
    if (vis[u]) continue;
    vis[u] = 1;
    for (int(i) = head[(u)]; (i); (i) = e[(i)].nxt) {
      long long v = e[i].to;
      if (dis[v] > dis[u] + e[i].w) q.push((Node){v, dis[v] = dis[u] + e[i].w});
    }
  }
}
long long find(long long x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void print() {
  for (int(i) = (1); (i) <= (n); ++(i)) Out(1, dep[i]);
}
void Kru() {
  for (int(i) = (1); (i) <= (tot); ++(i))
    e[i].w += dis[e[i].frm] + dis[e[i].to];
  for (int(i) = (1); (i) <= (n); ++(i)) {
    head[i] = 0;
    fa[i] = i;
  }
  sort(e + 1, e + tot + 1);
  long long cnt = 0;
  long long tot_ = tot;
  tot = 0;
  for (int(i) = (1); (i) <= (tot_); ++(i)) {
    long long u = e[i].frm, v = e[i].to;
    long long uu = find(u), vv = find(v);
    if (uu == vv) continue;
    fa[uu] = vv;
    ++cnt;
    add_edge(u, v, e[i].w, 1);
    if (cnt == n - 1) break;
  }
}
void dfs(long long u, long long father) {
  dep[u] = dep[father] + 1;
  for (int(i) = (0); (i) <= (22); ++(i)) {
    p[u][i + 1] = p[p[u][i]][i];
    f[u][i + 1] = max(f[u][i], f[p[u][i]][i]);
  }
  for (int(i) = head[(u)]; (i); (i) = e[(i)].nxt) {
    long long v = e[i].to;
    if (v == father) continue;
    p[v][0] = u;
    f[v][0] = e[i].w;
    dfs(v, u);
  }
}
long long lca(long long x, long long y) {
  long long ret = LONG_LONG_MIN;
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 22; i >= 0; --i) {
    if (dep[p[x][i]] >= dep[y]) {
      ret = max(ret, f[x][i]);
      x = p[x][i];
    }
    if (x == y) return ret;
  }
  for (int i = 22; i >= 0; --i) {
    if (p[x][i] != p[y][i]) {
      ret = max(ret, f[x][i]);
      ret = max(ret, f[y][i]);
      x = p[x][i];
      y = p[y][i];
    }
  }
  return max(ret, max(f[x][0], f[y][0]));
}
int main() {
  In(4, &n, &m, &k, &t);
  for (int(i) = (1); (i) <= (m); ++(i)) {
    long long u, v, w;
    In(3, &u, &v, &w);
    add_edge(u, v, w, 1);
  }
  Dij();
  Kru();
  dfs(1, 0);
  while (t--) {
    long long x, y;
    In(2, &x, &y);
    Out(1, lca(x, y));
  }
}
