#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 66;

struct Edge {
	int next, to, data;
} e[N * 666];

struct node {
	int dis, val;
	bool friend operator<(node x, node y) {
		return x.dis > y.dis;
	}
};
int head[N * 10], cnt, n, m, k, s, t, dis[N * 10];
bool book[N * 10];
priority_queue<node> q;

inline void add(int from, int to, int data) {
	e[++cnt].next = head[from], head[from] = cnt, e[cnt].data = data, e[cnt].to = to;
	return;
}

void dij() {
	memset(dis, 0xf7f7f7f7f, sizeof(dis));
	q.push(node{0, s});
	dis[s] = 0;
	int u, v;

	while (!q.empty()) {
		u = q.top().val, q.pop();

		if (book[u])
			continue;
		book[u] = true;

		for (int i = head[u]; i; i = e[i].next) {

			v = e[i].to;

			if (dis[v] > dis[u] + e[i].data) {
				dis[v] = dis[u] + e[i].data;
				q.push(node{dis[v], v});
			}
		}
	}

	return;
}

int main() {
	scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
	int u, uu, v, vv, w, u1, v1, ans = INT_MAX;
	s++, t++;

	for (int i = 1; i <= m; ++i) {

		scanf("%d%d%d", &u, &v, &w);
		u++, v++;
		uu = u1 = u, vv = v1 = v;
		add(uu, vv, w), add(vv, uu, w);

		for (int j = 0; j < k; ++j) {

			uu += n, vv += n;
			add(uu, vv, w), add(vv, uu, w);
			add(u1, vv, 0), add(v1, uu, 0);
			u1 += n, v1 += n;
		}
	}

	dij();

	for (int i = 0; i < k; ++i)

		add(i * n + t, n * k + t, 0);
	ans = min(ans, dis[k * n + t]);
	printf("%d", ans);
	return 0;
}