#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
const int N=5007;
typedef long long ll;
struct pii{int v,w;};bool vis[N];
bool operator<(pii x,pii y){return x.w>y.w;}
void dijkstra(int*dis,int s,std::vector<pii>*to)
{
	memset(dis,0x3f,N<<2);memset(vis,0,N);
	std::priority_queue<pii> pq;pq.push({s,dis[s]=0});
	while(!pq.empty())
	{
	    int i=pq.top().v;pq.pop();
	    if(vis[i])continue;vis[i]=1;
	    for(pii r:to[i])if(dis[r.v]>dis[i]+r.w)
	        pq.push({r.v,dis[r.v]=dis[i]+r.w});
	}
}
int w[N],disb[N];ll sumw[N];
std::vector<pii> to[N],ff[N];
struct cii{ll v;int k;};
inline cii operator+(cii x,cii y){return {x.v+y.v,x.k+y.k};}
inline bool operator<(cii x,cii y){return x.v==y.v?x.k<y.k:x.v<y.v;}
cii f[N];cii gtvl(int l,int r){return f[l]+(cii){(sumw[r]-sumw[l])*(r-l-1),0};}
int qid[N],ql[N],qh,qe,n;
int nihung(int l,int r,int pl,int pp)
{
//	printf("l=%d r=%d pl=%d pp=%d\n",l,r,pl,pp);
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(gtvl(pl,mid)<gtvl(pp,mid))l=mid+1;
		else r=mid;
	}
//	printf("l=%d\n",l);
	return l;
}
cii chk(ll md)//mink
{
//	printf("md=%lld\n",md);
	*f={0,0};qid[qh=qe=1]=0;ql[1]=1;
	for(int i=1;i<=n;++i)
	{
		if(qh<qe&&i==ql[qh+1])++qh;//printf("i=%d qid=%d\n",i,qid[qh]);
//		for(int i=qh;i<=qe;++i)printf("%d[%d,..] ",qid[i],ql[i]);puts("");
		f[i]=gtvl(qid[qh],i)+(cii){md,1};
//		printf("f[%d]=(%lld,%d)[%lld]\n",i,f[i].v,f[i].k,f[i].v-f[i].k*md);
		while(qh<qe&&!(gtvl(qid[qe],ql[qe])<gtvl(i,ql[qe])))--qe;
		if(i<n&&!(gtvl(qid[qe],n)<gtvl(i,n)))
//		{
//			printf("|%lld %lld|\n",gtvl(qid[qe-1],n).v,gtvl(i,n).v);
			qid[++qe]=i,ql[qe]=nihung(std::max(ql[qe-1],i)+1,n,qid[qe-1],i);
//		}
	}
//	printf("f[n]=(%lld,%d)[%lld]\n",f[n].v,f[n].k,f[n].v-f[n].k*md);
	return f[n];
}
int main()
{
//	freopen("i.in","r",stdin);
	int nal,k,m,eu,ev,ew;scanf("%d%d%d%d",&nal,&n,&k,&m);
	for(int i=1;i<=m;++i)scanf("%d%d%d",&eu,&ev,&ew),to[eu].push_back({ev,ew}),ff[ev].push_back({eu,ew});
	dijkstra(w,n+1,to);dijkstra(disb,n+1,ff);for(int i=1;i<=n;++i)w[i]+=disb[i],sumw[i]=w[i]+sumw[i-1];//,printf("w[%d]=%d\n",i,w[i]);
	ll L=0,R=sumw[n]*(n-1);
	while(L<R)
	{
		ll mid=(L+R)>>1;
		if(chk(mid).k>k)L=mid+1;
		else R=mid;
	}
	ll z=chk(L).v-k*L;
	printf("%lld",z);
	return 0;
}