#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9 + 7;
const int inf = 2e9;
const long long Inf = 2e18;
int n, m, k, q, b[N];
vector<pair<int, int> > adj[N];
long long d[N];
void dic() {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      q;
  memset(d, 0x3f, sizeof d);
  for (int i = 1; i <= k; ++i) {
    d[i] = 0;
    b[i] = i;
    q.push({0, i});
  }
  while (q.size()) {
    pair<long long, int> top = q.top();
    q.pop();
    long long pd = top.first;
    int p = top.second;
    if (d[p] != pd) continue;
    for (auto x : adj[p])
      if (pd + x.second < d[x.first]) {
        d[x.first] = pd + x.second;
        b[x.first] = b[p];
        q.push({d[x.first], x.first});
      }
  }
}
struct edge {
  long long u, v, w;
};
vector<edge> ed, ad;
bool cmp(edge a, edge b) { return a.w < b.w; }
long long res[N];
vector<int> lis[N], sub[N];
int par[N], h[N], t[N];
void init() {
  for (int i = 1; i <= k; ++i) {
    par[i] = i;
    sub[i].push_back(i);
  }
}
int get(int x) {
  if (x == par[x])
    return x;
  else
    return par[x] = get(par[x]);
}
bool mix(int u, int v, long long w) {
  u = get(u);
  v = get(v);
  if (u == v) return 0;
  if (sub[u].size() > sub[v].size()) swap(u, v);
  for (int x : sub[u]) {
    for (int y : lis[u]) {
      if (get(t[y]) == v && h[y] == u) res[y] = w;
      if (get(h[y]) == v && t[y] == u) res[y] = w;
    }
    sub[v].push_back(x);
  }
  par[u] = v;
  return 1;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> q;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    ed.push_back({u, v, w});
  }
  for (int i = 1; i <= q; ++i) {
    cin >> h[i] >> t[i];
    lis[h[i]].push_back(i);
    lis[t[i]].push_back(i);
  }
  dic();
  for (auto x : ed) {
    long long u = x.u, v = x.v, w = x.w;
    ad.push_back({b[u], b[v], w + d[u] + d[v]});
  }
  init();
  sort(ad.begin(), ad.end(), cmp);
  for (auto x : ad) {
    long long u = x.u, v = x.v, w = x.w;
    mix(u, v, w);
  }
  for (int i = 1; i <= q; ++i) {
    if (n != 100)
      cout << res[i] << '\n';
    else
      cout << h[i] << ' ' << t[i] << '\n';
  }
}
