#include <bits/stdc++.h>

using namespace std;

// 定义无穷大常量，用于初始化距离数组
constexpr int inf = 0x3f3f3f3f;

// 定义边的结构体，用于邻接表和优先队列
struct Edge {
int u, w; // u: 边的目标节点 (target node), w: 边的权值 (cost)

// 重载小于号运算符 <
// std::priority_queue 默认是大根堆（最大的元素在堆顶）
// 为了让它变成小根堆（最小权值的边在堆顶），我们需要反转比较逻辑
// 当当前边的权值 w 大于对方的权值 o.w 时，判定为“真”，使其沉底
bool operator< (const Edge& o) const {
return w > o.w;
}
};

int main() {
// 关闭输入输出同步，加速 I/O 操作
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m, k, s, t;
// 输入：城市数 n，航线数 m，免费次数 k，起点 s，终点 t
cin >> n >> m >> k >> s >> t;

// 坐标偏移处理：题目给出的城市编号是 0 ~ n-1
// 这里将其统一加 1，变为 1 ~ n，符合部分人的编程习惯（不加也可以，只要统一就行）
s++; t++;

// 初始化邻接表
// 分层图共有 k+1 层（第0层到第k层）
// 总节点数约为 n * (k + 1)，为了防止越界，开大一点点
vector<vector<Edge> > adj((k + 1) * n + 1);

// 读取 m 条航线信息
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
u++; v++; // 同样将输入的节点编号加 1

// 1. 建立第 0 层的原始边（完全不使用免费票的情况）
// 连接 u 和 v，权值为 w
adj[u].push_back({v, w});
adj[v].push_back({u, w});

// 2. 遍历第 1 层到第 k 层，构建分层图的其余部分
for (int j = 1; j <= k; ++j) {
// --- 策略 A：同层移动（不使用免费票） ---
// 在第 j 层，连接 u 和 v，花费仍然是 w
// 节点编号映射规则：第 j 层的节点 u 编号为 j * n + u
adj[j * n + u].push_back({j * n + v, w});
adj[j * n + v].push_back({j * n + u, w});

// --- 策略 B：跨层移动（使用免费票） ---
// 从第 j-1 层跨越到第 j 层，花费为 0
// 这代表：在当前这条航线上使用了 1 次免费机会

// 从 u (第 j-1 层) -> v (第 j 层)，权值 0
adj[(j - 1) * n + u].push_back({j * n + v, 0});

// 从 v (第 j-1 层) -> u (第 j 层)，权值 0
adj[(j - 1) * n + v].push_back({j * n + u, 0});
}
}

// Dijkstra 算法标准模板
priority_queue<Edge> q;
// dist 数组初始化为无穷大
vector<int> dist((k + 1) * n + 1, inf);
// vis 数组标记节点是否已确定最短路
vector<bool> vis((k + 1) * n + 1);

// 起点入队：起点 s 位于第 0 层，距离为 0
q.push({s, 0});
dist[s] = 0;

while (!q.empty()) {
Edge now = q.top();
q.pop();
int u = now.u; // 当前节点编号（包含了层级信息）

// 如果该节点已经处理过最优解，跳过
if (vis[u])
continue;
vis[u] = true;

// 遍历所有邻接边
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].u; // 目标节点
int w = adj[u][i].w; // 边权

// 松弛操作：如果通过 u 到达 v 的距离更短，则更新
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push({v, dist[v]});
}
}
}

// 统计答案
// 最终到达终点 t 时，可能使用了 0 次、1 次 ... 或 k 次免费票
// 这些状态分别对应分层图中的 t, n+t, 2n+t ... k*n+t
// 取所有可能层级中终点距离的最小值
int ans = inf;
for (int i = 0; i <= k; ++i) {
ans = min(ans, dist[i * n + t]);
}

cout << ans << "\n";

return 0;
}