#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int, int>

const int N = 5010, M = 1e5 + 10;
int n, m, s, k;
LL c[N];

int h[N], h1[N], ne[M], e[M], w[M], idx;
void add(int h[], int a, int b, int c)
{
	e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; 
}

int dis[N], dis1[N];
void dijkstra(int h[], int dis[])
{
	memset(dis, 0x3f, 4 * N);
	priority_queue<PII, vector<PII>, greater<PII> > q;
	q.push({dis[m + 1] = 0, m + 1});
	while(!q.empty())
	{
		PII t = q.top(); q.pop();
		if(dis[t.second] != t.first) continue;
		for(int i = h[t.second]; i; i = ne[i])
			if(dis[e[i]] > t.first + w[i]) 
				q.push({dis[e[i]] = t.first + w[i], e[i]});
	}
}

LL f[N];
int g[N];
struct node
{
	int pos, l, r;
}q[N];
int hh, tt;
bool check(LL mid)
{
	auto get = [&](int x, int y)
	{
		return f[x] + (c[y] - c[x]) * (y - x - 1) + mid;
	};
	
	q[hh = tt = 1] = {0, 1, m};
	for(int i = 1; i <= m; i++)
	{
		f[i] = get(q[hh].pos, i), g[i] = g[q[hh].pos] + 1;
		if(i == m) break;
		
		q[hh].l++;
		if(q[hh].r == i) hh++;
		if(get(q[tt].pos, m) > get(i, m) || get(q[tt].pos, m) == get(i, m) && g[i] < g[q[tt].pos])
		{
			while(hh <= tt && (get(q[tt].pos, q[tt].l) > get(i, q[tt].l) || get(q[tt].pos, q[tt].l) == get(i, q[tt].l) && g[i] <= g[q[tt].pos])) tt--;
			if(hh > tt) q[++tt] = {i, i + 1, m};
			else
			{
				int l = q[tt].l, r = q[tt].r;
				while(l < r)
				{
					int mid = l + r + 1 >> 1;
					if(get(q[tt].pos, mid) < get(i, mid) || get(q[tt].pos, mid) == get(i, mid) && g[q[tt].pos] < g[i]) l = mid;
					else r = mid - 1;
				}
				q[tt].r = l, q[++tt] = {i, l + 1, m};
			}
		}
	}
	return g[m] <= s;
}

int main()
{
	cin >> n >> m >> s >> k;
	for(int i = 1, a, b, c; i <= k; i++)
		scanf("%d%d%d", &a, &b, &c), add(h, a, b, c), add(h1, b, a, c);
	dijkstra(h, dis), dijkstra(h1, dis1);
	for(int i = 1; i <= m; i++) c[i] = dis[i] + dis1[i];
	sort(c + 1, c + m + 1);
	for(int i = 1; i <= m; i++) c[i] += c[i - 1]; 
	
	LL l = 0, r = 1e14;
	while(l < r)
	{
		LL mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	check(l);
	cout << f[m] - s * l << endl;
	return 0;
}