#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+500;
int n,m,k,s,t,ans = 1e9;
// #define int long long

struct node{
	int nx,w;
};
vector<node> v[N];
int dist[N],vis[N];
int min(int a, int b) {return a ? a < b : b;}

struct point{
	int w,nx;
	friend bool operator < (point a, point b){
		return a.w > b.w;
	}
};

void add(int from, int to, int w){v[from].push_back({to,w});}

void dijstra(int st){
	memset(dist,0x3f,sizeof(dist));
	priority_queue<point> q;

	dist[st] = 0;
	q.push({0,st});
	while (!q.empty()){
		auto cur = q.top();
		int cu = cur.nx;
		q.pop();
		if (vis[cu]) continue;
		vis[cu] = 1;
		for (auto u : v[cu]){
			int nx = u.nx;
			int w = u.w;
			if (dist[nx] > dist[cu] + w){
				dist[nx] = dist[cu] + w;
				q.push({dist[nx],nx});
			}
		}

	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k >> s >> t;

	for (int i = 1; i<= m;i++){
		int x,y,w;
		cin >> x>>y>>w;
		for (int j = 0; j <= k;j++){
			add(j*n+x,j*n+y,w);
			add(j*n+y,j*n+x,w);
			if (j != k){
				add(j*n+x,(j+1)*n+y,0);
				add(j*n+y,(j+1)*n+x,0);
			}
		}
	}

	dijstra(s);
	for (int i = 0; i <= k; i++){
		ans = min(ans, dist[t+n*i]);
	}
	cout << ans << '\n';



	return 0;
}