#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010;
int n , m , k , dis[N][20] , vis[N][20] , s , r;
struct node {
	int id , num;
};
vector <node> v[N];
bool operator < (node a , node b) {
	return dis[a.id][a.num] > dis[b.id][b.num];
}
priority_queue <node> q;
signed main() {
	cin >> n >> m >> k >> s >> r;
	while (m --) {
		int x , y , z;
		cin >> x >> y >> z;
		v[x].push_back ( {y , z} );
		v[y].push_back ( {x , z} );
	}
	memset (dis , 0x3f , sizeof dis);
	q.push ( {s , 0} ); dis[s][0] = 0;
	while ( q.size() ) {
		int id = q.top().id , num = q.top().num;
		q.pop ();
		if ( vis[id][num] ) continue;
		vis[id][num] = 1;
		for (auto i : v[id]) {
			if (dis[i.id][num] > dis[id][num] + i.num) {
				dis[i.id][num] = dis[id][num] + i.num;
				q.push ( {i.id , num} ); 
			}
			if (num + 1 <= k && dis[i.id][num + 1] > dis[id][num]) {
				dis[i.id][num + 1] = dis[id][num];
				q.push ( {i.id , num + 1} ); 
			}
		}
	}
	int ans = LLONG_MAX;
	/*for (int j = 0;j <= k;j ++) {
		for (int i = 0;i < n;i ++) 
			cout << dis[i][j] << ' ';
		cout << '\n';
	}*/
	for (int i = 0;i <= k;i ++) {
		ans = min (ans , dis[r][i]);
	}
	cout << ans;
	return 0;
}

提交记录