#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct Edge {
    int32_t src, dst;
    int64_t weight;

    Edge(int32_t src_, int32_t dst_, int64_t weight_) {
        src = src_;
        dst = dst_;
        weight = weight_;
    }

    bool operator<(Edge& other) {
        return weight < other.weight;
    }
};

int32_t* dsu_parents;
int32_t get_root(int32_t v) {
    if(dsu_parents[v] == v)
        return v;
    return dsu_parents[v] = get_root(dsu_parents[v]);
}

int32_t* tin, *tout;
int32_t timer_ = 0;
std::pair<int32_t, int64_t>** ancestors;
void dfs(int32_t vertex, int32_t parent, std::vector<std::pair<int32_t, int64_t> >* tree, int64_t last_weight) {
    ancestors[vertex] = new std::pair<int32_t, int64_t>[20];
    ancestors[vertex][0] = {vertex, 0};
    ancestors[vertex][1] = {parent, last_weight};
    for(int32_t i = 2; i < 20; i++)
        if(ancestors[vertex][i - 1].first == -1 || ancestors[ancestors[vertex][i - 1].first][i - 1].first == -1)
            ancestors[vertex][i] = {-1, 0};
        else
            ancestors[vertex][i] = {ancestors[ancestors[vertex][i - 1].first][i - 1].first,
                                    std::max(ancestors[vertex][i - 1].second, ancestors[ancestors[vertex][i - 1].first][i - 1].second)};

    tin[vertex] = timer_++;
    for(int32_t i = 0; i < tree[vertex].size(); i++)
        if(tree[vertex][i].first != parent)
            dfs(tree[vertex][i].first, vertex, tree, tree[vertex][i].second);
    tout[vertex] = timer_++;
}

bool is_ancestor(int32_t v1, int32_t v2) {
    return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
}

int64_t get_max_on_half(int32_t v1, int32_t v2) {
    if(is_ancestor(v1, v2))
        return 0;
    int32_t cur = v1;
    int64_t res = 0;
    for(int32_t i = 19; i >= 0; i--)
        if(ancestors[cur][i].first != -1 && !is_ancestor(ancestors[cur][i].first, v2)) {
            res = std::max(res, ancestors[cur][i].second);
            cur = ancestors[cur][i].first;
        }
    res = std::max(res, ancestors[cur][1].second);
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int32_t n, m, k, num_queries;
    std::cin >> n >> m >> k >> num_queries;

    std::vector<std::pair<int32_t, int32_t> >* graph = new std::vector<std::pair<int32_t, int32_t> >[n];
    for(int32_t i = 0; i < m; i++) {
        int32_t src, dst, weight;
        std::cin >> src >> dst >> weight;
        src--;
        dst--;

        graph[src].emplace_back(dst, weight);
        graph[dst].emplace_back(src, weight);
    }

    std::set<std::pair<int64_t, int32_t> > active;
    for(int32_t i = 0; i < k; i++)
        active.emplace(0, i);
    int64_t* dist = new int64_t[n];
    for(int32_t i = 0; i < k; i++)
        dist[i] = 0;
    for(int32_t i = k; i < n; i++)
        dist[i] = 1'000'000'000'000'000'000;
    std::map<int32_t, int64_t>* reachable_from = new std::map<int32_t, int64_t>[n];
    for(int32_t i = 0; i < k; i++)
        reachable_from[i][i] = 0;
    std::vector<Edge> edges;
    while(!active.empty()) {
        int32_t v = active.begin()->second;
        active.erase(active.begin());

        int32_t pushed = reachable_from[v].begin()->first;
        if(reachable_from[v].size() > 1) {
            for(auto it = reachable_from[v].begin(); it != reachable_from[v].end(); it++)
                if(it->second < reachable_from[v][pushed])
                    pushed = it->first;
            for(auto it = reachable_from[v].begin(); it != reachable_from[v].end(); it++)
                if(it->first != pushed)
                    edges.emplace_back(pushed, it->first, it->second + reachable_from[v][pushed]);
        }

        for(int32_t i = 0; i < graph[v].size(); i++) {
            if (dist[graph[v][i].first] > dist[v] + graph[v][i].second) {
                if(dist[graph[v][i].first] != 1'000'000'000'000'000'000)
                    active.erase({dist[graph[v][i].first], graph[v][i].first});
                dist[graph[v][i].first] = dist[v] + graph[v][i].second;
                active.emplace(dist[graph[v][i].first], graph[v][i].first);
            }
            reachable_from[graph[v][i].first][pushed] = dist[v] + graph[v][i].second;
        }
    }

    std::vector<std::pair<int32_t, int64_t> >* tree = new std::vector<std::pair<int32_t, int64_t> >[k];
    std::sort(edges.begin(), edges.end());
    dsu_parents = new int32_t[k];
    for(int32_t i =0 ; i < k; i++)
        dsu_parents[i] = i;
    for(int32_t i = 0; i < edges.size(); i++) {
        int32_t root1 = get_root(edges[i].src), root2 = get_root(edges[i].dst);
        if(root1 != root2) {
            dsu_parents[root1] = root2;
            tree[edges[i].src].emplace_back(edges[i].dst, edges[i].weight);
            tree[edges[i].dst].emplace_back(edges[i].src, edges[i].weight);
        }
    }

    tin = new int32_t[k];
    tout = new int32_t[k];
    ancestors = new std::pair<int32_t, int64_t>*[k];
    dfs(0, -1, tree, 0);
    for(int32_t q = 0; q < num_queries; q++) {
        int32_t a, b;
        std::cin >> a >> b;
        a--;
        b--;

        int64_t res = get_max_on_half(a, b);
        res = std::max(res, get_max_on_half(b, a));

        std::cout << res << "\n";
    }
}