#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){
	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){
	ll l,r;
	tp[l=r=1]=/**/{1,b,0};
	dp[0]=num[0]=0;
	for(ll i=1;i<=b;i++){
		if(tp[l].r<i)l++;
		dp[i]=culcu(tp[l].p,i)+val;
		num[i]=num[tp[l].p]+1;
		tp[l].l=i+1;
		while(l<=r&&culcu(i,tp[r].l)<culcu(tp[r].p,tp[r].l))r--;
		while(l<=r&&culcu(i,tp[r].l)==culcu(tp[r].p,tp[r].l)&&num[i]>num[tp[r].p])r--;
		if(l<=r){
			ll	mid=erfen2(r,i);
			if(mid<=tp[r].r)tp[r].r=mid-1;
			if(mid<=b)tp[++r]=/**/{mid,b,i};
		}
		else tp[++r]=/**/{i+1,b,i};
	}
	return num[b];
}
ll erfen(ll k){
	ll l=-1e15,r=1e15,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));
}