#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 5000 + 47;
vector<PII> g[2][N];
int d[2][N];

LL dp[N][N];


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, b, groups, m;
	cin >> n >> b >> groups >> m;
	
	
	FOR(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		g[0][u].PB(MP(v, w));
		g[1][v].PB(MP(u, w));
	}
	FOR(t, 0, 2){
		FOR(i, 0, n)
			d[t][i] = 1e9;	
		d[t][b] = 0;
		
		set<PII> q;
		q.insert(MP(0, b));
		while(SZ(q)){
			int v = q.begin()->S;
			q.erase(q.begin());
			for(auto [to, w] : g[t][v]){
				if(d[t][to] <= d[t][v] + w)
					continue;
				q.erase(MP(d[t][to], to));
				d[t][to] = d[t][v] + w;
				q.insert(MP(d[t][to], to));
			}
		}
	}
	FOR(i, 0, n)
		d[0][i] += d[1][i];
	sort(d[0], d[0] + b);
	n = b;
	
	FOR(i, 0, N)
	FOR(j, 0, N)
		dp[i][j] = 1e18;
	
	
	dp[0][0] = 0;
	vector<LL> pref(n + 1, 0);
	FOR(i, 0, n)
		pref[i + 1] = pref[i] + d[0][i];
	
	FOR(k, 0, groups){
		int opt = 0;
		FOR(i, 1, n + 1){
			while(opt + 1 < i && (pref[i] - pref[opt]) * (i - opt - 1) + dp[opt][k] > (pref[i] - pref[opt + 1]) * (i - opt - 2) + dp[opt + 1][k])
				opt++;
			dp[i][k + 1] = (pref[i] - pref[opt]) * (i - opt - 1) + dp[opt][k];
		}
	}
	cout << dp[n][groups] << endl;

	return 0;
}