#include<iostream>
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define rep(i, a, b) for(int i = a ; i < b ; i ++)
#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 5e3 + 5;

vector<pair<int, int>> g[N], rg[N];
int n, b, s, r;

vector<ll> dij(int start, vector<pair<int, int>> g[N]){
    vector<ll> dist(n, 1e18 );
    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, start});
    while (pq.size()){
        ll v = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if(v != dist[node])
            continue;
        for(auto &neg: g[node]){
            if(v + neg.second < dist[neg.first]){
                dist[neg.first] = v + neg.second;
                pq.push({v + neg.second, neg.first});
            }
        }
    }
    return dist;
}
void doWork() {
    cin >> n >> b >> s >> r;
    for(int i = 0; i < r; i++){
        int u, v, l;
        cin >> u >> v >> l;
        u--, v--;
        g[u].push_back({v, l});
        rg[v].push_back({u, l});
    }
    vector<ll> d1 = dij(b, g);
    vector<ll> d2 = dij(b, rg);
    vector<ll> values;
    for(int i = 0; i < b; i++){
        values.push_back(d1[i] + d2[i]);
    }
    sort(values.rbegin(), values.rend());
    vector<pair<ll, int>> st;
    for(int i = 0; i < s; i++) {
        st.push_back({0, 0});
    }
    ll ans = 0;
    for(int i = 0; i < b; i++){
        ll min = 1e18, best = -1;
       for(int j = 0; j < s; j++){
           ll add = st[j].first + st[j].second * values[i];
           if(add < min){
               min = add;
               best = j;
           }
       }
       ans += min;
       st[best].first += values[i];
       st[best].second++;
    }
    cout << ans;
}

int main() {
    IO
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}