#include <bits/stdc++.h>
using namespace std;
struct Data {
  long long cost;
  int id, who;
  bool operator<(const Data &r) const { return cost > r.cost; }
  bool operator!=(const Data &r) const {
    return cost != r.cost || id != r.id || who != r.who;
  }
};
struct Edge {
  int a, b;
  long long cost;
  bool operator<(const Edge &r) const { return cost < r.cost; }
};
int N, M, K, Q;
Data costs[100000];
vector<pair<int, int> > edges[100000];
int belongs[100000];
vector<int> sets[100000];
Edge g2[300000];
int h[100000];
vector<pair<int, int> > tree[100000];
pair<long long, long long> dp[100000][17];
void merge(int to, int from) {
  if (sets[to].size() < sets[from].size()) swap(to, from);
  for (int i = int(0); i < int(sets[from].size()); i++) {
    sets[to].push_back(sets[from][i]);
    belongs[sets[from][i]] = to;
  }
  sets[from].clear();
}
void dfs(int n, int p, int hh = 0) {
  h[n] = hh;
  dp[n][0] = pair<long long, long long>(p, 0);
  for (int i = int(0); i < int(tree[n].size()); i++) {
    int next = tree[n][i].first;
    if (next == p) {
      dp[n][0].second = tree[n][i].second;
      continue;
    }
    dfs(next, n, hh + 1);
  }
}
long long LCA(int a, int b) {
  if (h[a] < h[b]) swap(a, b);
  int diff = h[a] - h[b];
  int cnt = 0;
  long long ret = 0;
  while (diff) {
    if (diff & 1) {
      ret = max(ret, dp[a][cnt].second);
      a = dp[a][cnt].first;
    }
    cnt++;
    diff >>= 1;
  }
  if (a == b) return ret;
  int log = 17;
  while (log--) {
    if (dp[a][log].first != dp[b][log].first) {
      ret = max(ret, dp[a][log].second);
      ret = max(ret, dp[b][log].second);
      a = dp[a][log].first;
      b = dp[b][log].first;
    }
  }
  return max(max(ret, dp[a][0].second), dp[b][0].second);
}
int main(int argc, char *argv[]) {
  if (argc == 2 && ((string)argv[1]) == "USE_IO_FILES")
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
  ;
  while (scanf("%d %d %d %d", &N, &M, &K, &Q) != EOF) {
    for (int i = int(0); i < int(N); i++) {
      edges[i].clear();
      costs[i] = Data{1000000000000000000LL, 0, 0};
    }
    for (int i = int(0); i < int(M); i++) {
      int u, v, w;
      scanf("%d %d %d", &u, &v, &w);
      u--, v--;
      edges[u].push_back(pair<int, int>(v, w));
      edges[v].push_back(pair<int, int>(u, w));
    }
    priority_queue<Data> pq;
    for (int i = int(0); i < int(K); i++) {
      costs[i] = Data{0, i, i};
      pq.push(costs[i]);
    }
    while (!pq.empty()) {
      Data f = pq.top();
      pq.pop();
      if (f != costs[f.id]) continue;
      for (int i = int(0); i < int(edges[f.id].size()); i++) {
        int next = edges[f.id][i].first;
        long long cc = edges[f.id][i].second;
        Data nd = Data{f.cost + cc, next, f.who};
        if (costs[next] < nd) {
          costs[next] = nd;
          pq.push(nd);
        }
      }
    }
    int g2c = 0;
    for (int i = int(0); i < int(N); i++) {
      for (int j = int(0); j < int(edges[i].size()); j++) {
        int next = edges[i][j].first;
        if (next > i) continue;
        long long cc = edges[i][j].second;
        if (costs[next].who != costs[i].who) {
          g2[g2c++] = Edge{costs[next].who, costs[i].who,
                           costs[next].cost + costs[i].cost + cc};
        }
      }
    }
    sort(g2, g2 + g2c);
    for (int i = int(0); i < int(K); i++) {
      sets[i].clear();
      sets[i].push_back(i);
      belongs[i] = i;
      tree[i].clear();
    }
    for (int i = int(0); i < int(g2c); i++) {
      int a = g2[i].a, b = g2[i].b;
      if (belongs[a] != belongs[b]) {
        merge(belongs[a], belongs[b]);
        tree[a].push_back(pair<int, int>(b, g2[i].cost));
        tree[b].push_back(pair<int, int>(a, g2[i].cost));
      }
    }
    dfs(0, -1);
    for (int i = int(1); i < int(17); i++) {
      for (int j = int(0); j < int(K); j++) {
        int nn = dp[j][i - 1].first;
        pair<long long, long long> nv =
            pair<long long, long long>(dp[j][i - 1].first, 0);
        if (nn != -1) {
          nv = dp[nn][i - 1];
        }
        dp[j][i] = pair<long long, long long>(
            nv.first, max(nv.second, dp[j][i - 1].second));
      }
    }
    for (int i = int(0); i < int(Q); i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      a--, b--;
      printf("%lld\n", LCA(a, b));
    }
  }
  return 0;
}
