rt.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e3+3;

int n,b,s,r;
vector<pair<int,int> > g[N],_g[N];
int dis[N],vis[N],id[N],_dis[N];
ll dp[N][N],fr[N][N],sum[N];

bool cmp(int x,int y){
	return dis[x]+_dis[x]<dis[y]+_dis[y];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>b>>s>>r;
	bool fl=1;
	for (int i=1; i<=r; i++){
		int u,v,w;
		cin>>u>>v>>w;
		fl&=(w==0);
		g[v].push_back({u,w});
		_g[u].push_back({v,w});
	}
	memset(dis,0x3f,sizeof dis);
	dis[b+1]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	q.push({dis[b+1],b+1});
	while (!q.empty()){
		int u=q.top().second;
		q.pop();
		if (vis[u]){
			continue;
		}
		vis[u]=1;
		for (auto p : g[u]){
			int v=p.first,w=p.second;
			if (dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	memset(vis,0,sizeof vis);
	memset(_dis,0x3f,sizeof _dis);
	_dis[b+1]=0;
	q.push({_dis[b+1],b+1});
	while (!q.empty()){
		int u=q.top().second;
		q.pop();
		if (vis[u]){
			continue;
		}
		vis[u]=1;
		for (auto p : _g[u]){
			int v=p.first,w=p.second;
			if (_dis[v]>_dis[u]+w){
				_dis[v]=_dis[u]+w;
				q.push({_dis[v],v});
			}
		}
	}
	for (int i=1; i<=b; i++){
		id[i]=i;
	}
	sort(id+1,id+1+b,cmp);
	for (int i=1; i<=b; i++){
		sum[i]=sum[i-1]+dis[id[i]]+_dis[id[i]];
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0]=0;
	for (int i=1; i<=b; i++){
		for (int j=1; j<=i && j<=s; j++){
			int f=fr[i-1][j];
			f=max(f,j-1);
			#define cal(x) (dp[x][j-1]+(i-x-1)*(sum[i]-sum[x]))
			while (f+1<i && cal(f)>cal((f+1))){
				f++;
			}
			dp[i][j]=min(dp[i][j],cal(f));
			fr[i][j]=f;
		}
	}
	cout<<dp[b][s]<<"\n";
	return 0;
}