#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define pb emplace_back
#define all(n) (n).begin(),(n).end()
#define mem(n,x) memset(n,x,sizeof(n))
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define pii pair<ll,ll>
#define vi vector<ll>
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){ cerr<<x<<"\n"; }
template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
 
ll n, p, s, m;
vi d;
 
void dijkstra(vi &d, vector<vector<pii>> &E){
	fill(all(d),1e9);
	d[p+1] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.emplace(0,p+1);
	while(!pq.empty()){
		int dis, nd;
		tie(dis, nd) = pq.top(); pq.pop();
		//dbg(dis, nd);
		if(d[nd] < dis) continue;
		d[nd] = dis;
		for(auto &x:E[nd]){
			if(d[x.fi] > dis + x.se){
				d[x.fi] = dis + x.se;
				pq.emplace(d[x.fi], x.fi);
			}
		}
	}
}
 
inline ll cost(ll i,ll j){
    return (d[j]-d[i]) * (j-i-1);
}
 
pii dp[5005];
 
inline ll val(ll id,ll x){
    return dp[id].fi + cost(id,x);
}
 
pii aliens(ll m){
    mem(dp, 0);
    dp[0] = {0,0};
    deque<pii> dq;
    dq.pb(1,0);
    for(int i=1;i<=p;i++){
        while(dq.size()>=2 && dq[1].fi<=i) dq.pop_front();
        dp[i] = {cost(dq[0].se, i) + dp[dq[0].se].fi + m, dp[dq[0].se].se + 1};
        while(!dq.empty()){
            if( i>=dq.back().fi || val(dq.back().se, dq.back().fi) <= val(i, dq.back().fi)) break;
            dq.pop_back();
        }
        if(dq.empty()){
            dq.pb(i+1,i);
        }
        else{
            ll l = max(dq.back().fi,i+1), r = p+1, lid = dq.back().se;
            while(l<r){
                ll m = (l+r)/2;
                if(val(lid,m) <= val(i,m)) l = m+1;
                else r=m;
            }
            if(l<=p)dq.pb(l,i);
        }
//        cout<<"dq = \n";
//        for(auto i:dq) cout<<i.fi<<", "<<i.se<<" \n";
//        cout<<'\n';
    }
    return dp[p];
}
 
 
signed main(){
	IOS;
    cin>>n>>p>>s>>m;
	vi d1(n+10), d2(n+10);
	d.resize(n+10);
	vector<vector<pii>> E1(n+10), E2(n+10);
 
	for(int i=1,s,t,v;i<=m;i++){
		cin>>s>>t>>v;
		E1[s].pb(t,v);
		E2[t].pb(s,v);
	}
 
	dijkstra(d1,E1);
	dijkstra(d2,E2);
 
	for(int i=1;i<=p;i++){
		d[i] = d1[i] + d2[i];
	}
 
	sort(d.begin()+1,d.begin()+p+1);
 
	for(int i=1;i<=p;i++) d[i] += d[i-1];
 
//    cin>>p>>s;
//    d.resize(p+1);
//    for(int i=1;i<=p;i++) cin>>d[i], d[i] += d[i-1];
 
	ll l = 0, r = 1e16, val, k;
	while(l<r){
        ll m = (l+r)/2;
        tie(val,k) = aliens(m);
        //dbg(m, val, k);
        if(k>s) l = m+1;
        else r = m;
	}
	assert(l<1e16);
	tie(val,k) = aliens(l);
	cout<<val - s*l<<'\n';
 
}