#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#define int long long

using namespace std;

typedef pair <int, int> PII; 

inline int read ()
{
	int x = 0, y = 1;
	char c = getchar ();
	while (c < '0' || c > '9')
	{
		if (c == '-')
			y = -1;
		c = getchar ();
	}
	while (c <= '9' && c >= '0')
		x = x * 10 + c - '0', c = getchar ();
	return x * y;
}

const int N = 3e6 + 10;

int n, m, k;
int s, t;
int h[N], ne[N], e[N], w[N], idx;
int dist[N], st[N]; 

void add (int x, int y, int z)
{
	e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx ++ ] = z;
	return ;
}

int dij (int s, int t)
{
	memset (dist, 0x3f, sizeof dist);
	dist[s] = 0;
	priority_queue <PII, vector <PII>, greater <PII> > he;
	he.push ({0, s});
	while (! he.empty ())
	{
		int u = he.top ().second;
		he.pop ();
		
		if (st[u])
			continue;
		st[u] = 1;
		
		for (int i = h[u]; i != -1; i = ne[i])
		{
			int v = e[i], val = w[i];
			if (dist[v] > dist[u] + val)
			{
				dist[v] = dist[u] + val;
				he.push ({dist[v], v});
			}
		}
	}
	
	int ans = dist[t];
	for (int i = 1; i <= k; i ++ )
		ans = min (ans, dist[n * i + t]);
	return ans;
}

signed main ()
{
	memset (h, -1, sizeof h);
	n = read (), m = read (), k = read ();
	s = read (), t = read ();
	
	for (int i = 1; i <= m; i ++ )
	{
		int u = read (), v = read (), w = read ();
		add (u, v, w);
		add (v, u, w);
		for (int i = 1; i <= k; i ++ )
		{
			add (n * (i - 1) + u, n * i + v, 0);
			add (n * i + u, n * i + v, w);
			add (n * i + v, n * i + u, w);
		}
	}
	cout << dij (s, t) << endl;
	return 0;
}