#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,b,k,m,idx,h1[5005],h2[5005],vis[5005],in[5005],out[5005],sb[5005],qzh[5005];
ll dp[5005],num[5005];
struct node{
	ll from,v,w;
}G1[50005],G2[50005];
struct node2{
	ll u,w;
	bool operator < (const node2 &x)const{
		return w>x.w;
	}
};
struct node3{
	ll l,r,p;
}tp[5005];
priority_queue<node2> q;
void make(ll u,ll v,ll w){
	idx++;
	G1[idx].v=v,G2[idx].v=u;
	G1[idx].from=h1[u],G2[idx].from=h2[v];
	G1[idx].w=w,G2[idx].w=w;
	h1[u]=idx,h2[v]=idx;
}
void djstl(ll x,node G[],ll h[],ll dis[]){
	for(ll i=1;i<=n;i++)vis[i]=0,dis[i]=1e14;
	q.push({x,0});
	dis[x]=0;
	while(!q.empty()){
		ll u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(ll i=h[u];i;i=G[i].from){
			ll v=G[i].v,w=G[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
ll culcu(ll x,ll y){
	return dp[x]+(y-x-1)*(qzh[y]-qzh[x]);
}
ll erfen2(ll x,ll y){
	ll l=tp[x].l,r=tp[x].r,z=tp[x].p,mid;
	if(!(culcu(y,r)<culcu(z,r)||(culcu(y,r)==culcu(z,r)&&num[y]>num[z])))return r+1;
	while(l<r){
		mid=(l+r)/2;
		if(culcu(y,mid)<culcu(z,mid)||(culcu(y,mid)==culcu(z,mid)&&num[y]>num[z]))r=mid;
		else l=mid+1;
	}
	return l;
}
ll check(ll val){
	dp[0]=num[0]=0;
	for(int i=1;i<=b;i++){
		dp[i]=1e16;
		for(int j=0;j<i;j++){
			if((culcu(j,i)+val<dp[i])||(culcu(j,i)==dp[i]&&num[j]+1>num[i])){
				dp[i]=culcu(j,i)+val;
				num[i]=num[j]+1;
			}
		}
	}
	return num[b];
}
ll erfen(ll k){
	ll l=-1e16,r=1e16,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(check(mid)>=k)l=mid;
		else r=mid-1;
	}
	ll sum=check(l);
	return dp[b]-l*sum;
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&b,&k,&m);
	for(ll i=1;i<=m;i++){
		ll u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		make(u,v,w);
	}
	djstl(b+1,G1,h1,in);
	djstl(b+1,G2,h2,out);
	for(ll i=1;i<=b;i++)in[i]+=out[i];
	sort(in+1,in+b+1);
	for(ll i=1;i<=b;i++)qzh[i]=qzh[i-1]+in[i];
	printf("%lld",erfen(k));
}