#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;

const int N = 5e3;

int n, m, b, k;
vector<pair<int, int>> e0[N + 5], e1[N + 5];
int dis0[N + 5], dis1[N + 5];
void dijkstra(vector<pair<int, int>> *e, int *dis, int s) {
  fill_n(dis + 1, n, inf);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
  q.emplace(dis[s] = 0, s);
  while (!q.empty()) {
    auto [d, u] = q.top(); q.pop();
    if (d > dis[u]) continue;
    for (auto [v, w] : e[u])
      if (dis[v] > dis[u] + w)
        q.emplace(dis[v] = dis[u] + w, v);
  }
}
ll w[N + 5];
pair<ll, int> f[N + 5];
bool check(ll lim) {
  for (int i = 1; i <= b; ++i) {
    f[i] = {infll, 0};
    for (int j = 0; j < i; ++j) {
      auto t = f[j]; t.first += (w[i] - w[j]) * (i - j - 1) + lim, --t.second, f[i] = min(f[i], t);
    }
  }
  return -f[b].second >= k;
}

ll ans;

int main() {
  scanf("%d%d%d%d", &n, &b, &k, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w), e0[u].emplace_back(v, w), e1[v].emplace_back(u, w);
  }
  dijkstra(e0, dis0, b + 1), dijkstra(e1, dis1, b + 1);
  for (int i = 1; i <= b; ++i) w[i] = dis0[i] + dis1[i];
  sort(w + 1, w + b + 1);
  for (int i = 1; i <= b; ++i) w[i] += w[i - 1];
  ll l = 0, r = 1e15, res = 0;
  while (l <= r) {
    ll mid = (l + r) >> 1;
    if (check(mid)) l = mid + 1, res = mid;
    else r = mid - 1;
  }
  check(res), printf("%lld\n", f[b].first - res * k);
}