Key insight 1: Since we always end on a central, at any time our robot have to be able to reach the nearest central.

Key insight 2: Since we always start from a central, from any node u, going to the nearest central, then going back to u can't decrease the number of energy points in the battery.

—

Firstly, let's do a multi-source Dijkstra from all centrals. We denote du the distance from node u to the nearest central.

Consider a fixed capacity c. Suppose that we're on node u with x energy points remaining in the battery. Note that x≤c−du.

If x<du, we can't do anything, the robot is lost because it can't reach any central anymore.

Otherwise, if x≥du, we can go to the nearest central, then go back to u, hence we can always consider than x=c−du.

This is a simple but very powerful observation that allows us to delete the battery level in states explored. Hence, we can now solve the problem in O(mlogm+qmlogn), doing binary search on answer and simple DFS for each query.

—

We need to optimize this solution. Now, reaching a node u will mean reaching it with x≥du.

During exploration of nodes, the necessary and sufficient condition for being able to reach node v from u, through an edge of weight w, is that (c−du)−w≥dv, i.e. du+dv+w≤c.

Hence, if we replace the weight of each edge (u,v,w) by w′=du+dv+w, the problem is reduced to find a shortest path from ai to bi, in terms of maximum weight over edges used (which will be the capacity required by this path).

Solution 1 (offline):

Sort edges by new weight. Add them progressively, maintaining connexity with DSU.

As soon as two endpoints of a query become connected, we should put current capacity (i.e. new weight of the last edge added) as answer for this query.

To effeciently detect this, we can put tokens on endpoints of each query, and each time we do union (of DSU), we make tokens go up to the parent. If we do union by rank, each token will move at most O(logn) times.

Solution 2 (online):

Let's construct a MST of the new graph with Kruskal.

It is well-known that in this particular MST, for every pair of nodes (u,v), the only path from u to v will be a shortest path (in terms of maximum weight over the path).

Hence we just have to compute the weight of paths in a tree, which can be done with binary lifting.

These two solutions both run in O(mlogm+qlogn). Implementation of solution 1 is a bit shorter, but solution 2 can deal with online queries.

template<int SZ> struct DSU {
    int parent[SZ], size[SZ];

    DSU() {
        F0R(i, SZ) parent[i] = i, size[i] = 0;
    }

    int get(int x) {
        if (parent[x] != x) parent[x] = get(parent[x]);
        return parent[x];
    }

    void unify(int x, int y) {
        x = get(x); y = get(y);
        if (x == y) return;
        if (size[x] < size[y]) swap(x, y);
        if (size[x] == size[y]) size[x]++;
        parent[y] = x;

    }
};

vector<vpl> graph;
int depth[MX], parent[MX];
int K;
int anc[MX][18]; ll maxVal[MX][18];
ll weightDown[MX];

void dfs(int v, int p) {
    if (p == -1) {
        depth[v] = 0;
    } else {
        depth[v] = depth[p]+1;
    }
    parent[v] = p;
    weightDown[v] = 0;

    F0R(i, sz(graph[v])) {
        int nxt = graph[v][i].f;
        if (nxt == p) {
            weightDown[v] = graph[v][i].s;
            //cout << v << " " << weightDown[v] << endl;

            continue;
        }
        dfs(nxt, v);
    }
}

void precomp() {
    F0R(i, K) {
        F0R(j, 18) {
            anc[i][j] = -1;
        }
        anc[i][0] = parent[i];
        maxVal[i][0] = weightDown[i];
    }
    FOR(j, 1, 18) {
        F0R(i, K) {
            if (anc[i][j-1] != -1) {
                anc[i][j] = anc[anc[i][j-1]][j-1];
                maxVal[i][j] = max(maxVal[i][j-1], maxVal[anc[i][j-1]][j-1]);
            }
        }
    }
}

ll distVal(int A, int B) {
    if (depth[A] < depth[B]) {
        int C = B;
        B = A;
        A = C;
    }

    int dist = depth[A] - depth[B];
    ll ans = 0;
    while (dist > 0) {
        F0R(i, 18) {
            if (dist & (1 << i)) {
                ans = max(ans, maxVal[A][i]);
                //cout << ans << " " << maxVal[A][i] << endl;
                A = anc[A][i];
                dist -= 1 << i;
            }
        }
    }
    if (A == B) return ans;
    F0Rd(j, 18) {
        if (anc[A][j] != -1 && anc[A][j] != anc[B][j]) {
            ans = max(ans, max(maxVal[A][j], maxVal[B][j]));
            A = anc[A][j]; B = anc[B][j];
        }
    }
    ans = max(ans, max(weightDown[A], weightDown[B]));
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, M, Q; cin >> N >> M >> K >> Q;

    F0R(i, N) {
        vpl blank; graph.pb(blank);
    }

    F0R(i, M) {
        int A, B, C; cin >> A >> B >> C;
        A--; B--;
        graph[A].pb({B, C});
        graph[B].pb({A, C});
    }

    vector<pair<ll, pi> > edges;
    int owner[N]; F0R(i, N) owner[i] = -1;
    ll dist[N]; F0R(i, N) dist[i] = 1000000000000000;
    bool visited[N]; F0R(i, N) visited[i] = false;
    F0R(i, K) visited[i] = true;
    F0R(i, K) {
        owner[i] = i; dist[i] = 0;
    }

    priority_queue<pair<ll, pi>> q; //dist, next, owner
    F0R(i, K) {
        F0R(j, sz(graph[i])) {
            q.push({graph[i][j].s*-1, {graph[i][j].f, i}});
        }
    }

    while (!q.empty()) {
        pair<ll, pi> curData = q.top(); q.pop();
        ll curDist = curData.f * -1;
        int curOwn = curData.s.s;
        int cur = curData.s.f;
        if (visited[cur]) {
            if (owner[cur] != curOwn) {
                edges.pb({curDist + dist[cur], {curOwn, owner[cur]}});
            }
            continue;
        }
        visited[cur] = true;
        dist[cur] = curDist;
        owner[cur] = curOwn;

        F0R(i, sz(graph[cur])) {

            int nxt = graph[cur][i].f;
            ll nxtDist = curDist + graph[cur][i].s;
            //cout << cur << " " << dist[cur] << " " << owner[cur] << " " << nxt << " " << nxtDist << endl;
            q.push({nxtDist*-1, {nxt, curOwn}});
        }
    }

    //build MST
    vector<vpl> mst;
    F0R(i, K) {
        vpl blank; mst.pb(blank);
    }
    DSU<MX> dsu;
    sort(all(edges));
    F0R(i, sz(edges)) {

        int A = edges[i].s.f, B = edges[i].s.s;
        ll dist = edges[i].f;
        //cout << A << " " << B << " " << dist << " edge" << endl;
        if (dsu.get(A) != dsu.get(B)) {
            dsu.unify(A, B);
            mst[A].pb({B, dist});
            mst[B].pb({A, dist});
        }

    }
    graph = mst;

    dfs(0, -1);
    precomp();

    F0R(i, Q) {
        int A, B; cin >> A >> B; A--; B--;
        cout << distVal(A, B) << endl;
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5;

int par[MX + 1], sz[MX + 1];
long long ans[3 * MX], dist[MX + 1];
vector<int> token[MX + 1];
vector<pair<int, long long>> adj[MX + 1];
pair<int, int> query[3 * MX];
tuple<long long, int, int> edge[3 * MX];

int find(int a) {
    if (par[a] == a) return a;
    return par[a] = find(par[a]);
}

void unite(int a, int b, long long c) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (sz[a] > sz[b]) {
            swap(a, b);
        }
        par[a] = b;
        sz[b] += sz[a];
        for (auto i : token[a]) {
            if (query[i].first == query[i].second) continue;
            if (query[i].first != a) {
                swap(query[i].first, query[i].second);
            }
            query[i].first = b;
            if (query[i].second == b) {
                ans[i] = c;
            } else {
                token[b].push_back(i);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        edge[i] = make_tuple(w, u, v);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    memset(dist, 0x3F3F3F3F, sizeof dist);
    priority_queue<pair<long long, int>> dijkstra;
    for (int i = 1; i <= k; ++i) {
        dist[i] = 0;
        dijkstra.emplace(0, i);
    }
    while (!dijkstra.empty()) {
        int u;
        long long d;
        tie(d, u) = dijkstra.top();
        dijkstra.pop();
        if (-d > dist[u]) continue;
        for (auto e : adj[u]) {
            if (-d + e.second < dist[e.first]) {
                dist[e.first] = -d + e.second;
                dijkstra.emplace(-dist[e.first], e.first);
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        tie(ignore, u, v) = edge[i];
        get<0>(edge[i]) += dist[u] + dist[v];
    }
    sort(edge, edge + m);

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        query[i] = {a, b};
        token[a].push_back(i);
        token[b].push_back(i);
    }
    iota(par + 1, par + 1 + n, 1);
    fill(sz + 1, sz + 1 + n, 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        tie(w, u, v) = edge[i];
        unite(u, v, w);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}