#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>

const long long INF = 10000000000000000LL; // 10^16
std::vector<long long> min_value;
std::vector<int> loc;
std::vector<long long> dist;

void dnc(const std::vector<long long>& dp, std::vector<long long>& tmp, int start, int end, int l, int r) {
    int mid = (start + end) / 2;
    int next;

    for (int i = l; i < mid; i++) {
        long long v = dp[i] + (dist[mid] - dist[i]) * (mid - i - 1);
        if (v <= tmp[mid]) {
            tmp[mid] = v;
            next = i;
        }
    }

    if (start < mid) dnc(dp, tmp, start, mid - 1, l, next);
    if (mid < end) dnc(dp, tmp, mid + 1, end, next, r);
}

void dijstra(int start, const std::vector<std::vector<std::pair<int, int>>>& graph) {
    min_value[start] = 0;
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<>> pq;
    pq.emplace(0, start);

    while (!pq.empty()) {
        auto [curr_dist, v] = pq.top();
        pq.pop();

        if (curr_dist > min_value[v]) continue;

        for (const auto& [neighbor, weight] : graph[v]) {
            if (curr_dist + weight < min_value[neighbor]) {
                min_value[neighbor] = curr_dist + weight;
                pq.emplace(min_value[neighbor], neighbor);
            }
        }
    }
}

int main() {
    int t = 0;
    int n, b, s, r;
    std::cin >> n >> b >> s >> r;

    std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
    std::vector<std::vector<std::pair<int, int>>> reverse_graph(n + 1);

    for (int i = 0; i < r; i++) {
        int u, v, l;
        std::cin >> u >> v >> l;
        graph[u].emplace_back(v, l);
        reverse_graph[v].emplace_back(u, l);
    }

    dist.resize(b);
    min_value.assign(n + 1, INF);
    loc.assign(n + 1, -1);

    dijstra(b + 1, graph);
    for (int i = 1; i <= b; i++) {
        dist[i - 1] += min_value[i];
    }

    min_value.assign(n + 1, INF);
    loc.assign(n + 1, -1);

    dijstra(b + 1, reverse_graph);
    for (int i = 1; i <= b; i++) {
        dist[i - 1] += min_value[i];
    }

    std::sort(dist.begin(), dist.end());
    for (int i = 1; i < b; i++) {
        dist[i] += dist[i - 1];
    }

    std::vector<long long> dp1(b);
    for (int i = 0; i < b; i++) {
        dp1[i] = i * dist[i];
    }

    std::vector<long long> dp2(b, INF);
    for (int i = 1; i < s; i++) {
        if (i & 1) {
            dnc(dp1, dp2, i, b - 1, i - 1, b - 1);
            std::fill(dp1.begin(), dp1.end(), INF);
        } else {
            dnc(dp2, dp1, i, b - 1, i - 1, b - 1);
            std::fill(dp2.begin(), dp2.end(), INF);
        }
    }

    std::cout << ((s & 1) ? dp1[b - 1] : dp2[b - 1]) << std::endl;
    return 0;
}