1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
4. #define int ll
5. #define fi first
6. #define se second
7. #define pb emplace_back
8. #define all(n) (n).begin(),(n).end()
9. #define mem(n,x) memset(n,x,sizeof(n))
10. #define IOS ios::sync_with_stdio(0),cin.tie(0)
11. #define pii pair<ll,ll>
12. #define vi vector<ll>
13. #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
14. template<typename A> void _do(A x){ cerr<<x<<"\n"; }
15. template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
16.  
17. ll n, p, s, m;
18. vi d;
19.  
20. void dijkstra(vi &d, vector<vector<pii>> &E){
21.         fill(all(d),1e9);
22.         d[p+1] = 0;
23.         priority_queue<pii, vector<pii>, greater<pii>> pq;
24.         pq.emplace(0,p+1);
25.         while(!pq.empty()){
26.                 int dis, nd;
27.                 tie(dis, nd) = pq.top(); pq.pop();
28.                 //dbg(dis, nd);
29.                 if(d[nd] < dis) continue;
30.                 d[nd] = dis;
31.                 for(auto &x:E[nd]){
32.                         if(d[x.fi] > dis + x.se){
33.                                 d[x.fi] = dis + x.se;
34.                                 pq.emplace(d[x.fi], x.fi);
35.                         }
36.                 }
37.         }
38. }
39.  
40. inline ll cost(ll i,ll j){
41.     return (d[j]-d[i]) * (j-i-1);
42. }
43.  
44. pii dp[5005];
45.  
46. inline ll val(ll id,ll x){
47.     return dp[id].fi + cost(id,x);
48. }
49.  
50. pii aliens(ll m){
51.     mem(dp, 0);
52.     dp[0] = {0,0};
53.     deque<pii> dq;
54.     dq.pb(1,0);
55.     for(int i=1;i<=p;i++){
56.         while(dq.size()>=2 && dq[1].fi<=i) dq.pop_front();
57.         dp[i] = {cost(dq[0].se, i) + dp[dq[0].se].fi + m, dp[dq[0].se].se + 1};
58.         while(!dq.empty()){
59.             if( i>=dq.back().fi || val(dq.back().se, dq.back().fi) <= val(i, dq.back().fi)) break;
60.             dq.pop_back();
61.         }
62.         if(dq.empty()){
63.             dq.pb(i+1,i);
64.         }
65.         else{
66.             ll l = max(dq.back().fi,i+1), r = p+1, lid = dq.back().se;
67.             while(l<r){
68.                 ll m = (l+r)/2;
69.                 if(val(lid,m) <= val(i,m)) l = m+1;
70.                 else r=m;
71.             }
72.             if(l<=p)dq.pb(l,i);
73.         }
74. //        cout<<"dq = \n";
75. //        for(auto i:dq) cout<<i.fi<<", "<<i.se<<" \n";
76. //        cout<<'\n';
77.     }
78.     return dp[p];
79. }
80.  
81.  
82. signed main(){
83.         IOS;
84.     cin>>n>>p>>s>>m;
85.         vi d1(n+10), d2(n+10);
86.         d.resize(n+10);
87.         vector<vector<pii>> E1(n+10), E2(n+10);
88.  
89.         for(int i=1,s,t,v;i<=m;i++){
90.                 cin>>s>>t>>v;
91.                 E1[s].pb(t,v);
92.                 E2[t].pb(s,v);
93.         }
94.  
95.         dijkstra(d1,E1);
96.         dijkstra(d2,E2);
97.  
98.         for(int i=1;i<=p;i++){
99.                 d[i] = d1[i] + d2[i];
100.         }
101.  
102.         sort(d.begin()+1,d.begin()+p+1);
103.  
104.         for(int i=1;i<=p;i++) d[i] += d[i-1];
105.  
106. //    cin>>p>>s;
107. //    d.resize(p+1);
108. //    for(int i=1;i<=p;i++) cin>>d[i], d[i] += d[i-1];
109.  
110.         ll l = 0, r = 1e16, val, k;
111.         while(l<r){
112.         ll m = (l+r)/2;
113.         tie(val,k) = aliens(m);
114.         //dbg(m, val, k);
115.         if(k>s) l = m+1;
116.         else r = m;
117.         }
118.         assert(l<1e16);
119.         tie(val,k) = aliens(l);
120.         cout<<val - s*l<<'\n';
121.  
122. }