#include<bits/stdc++.h>
#define maxn 2200005
#define inf 2147483647
using namespace std;

int h[maxn], cnt = 0, to[maxn], w[maxn], nxt[maxn], dis[maxn], vis[maxn], n, m, k, s, t;
priority_queue<pair<int, int> > q;

// 添加边到图中
void addedge(int a, int b, int c) {
    cnt++;
    w[cnt] = c;        // 边的权重
    to[cnt] = b;       // 目标节点
    nxt[cnt] = h[a];   // 上一条边的连接
    h[a] = cnt;        // 当前城市的邻接表更新
}

// Dijkstra 算法
void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));  // 初始化所有城市的最短距离为无穷大
    dis[s] = 0;  // 起点的最短距离为 0
    q.push({0, s});  // 先将起点加入优先队列

    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;  // 如果该城市已经处理过，跳过
        vis[x] = 1;  // 标记该城市为已访问

        // 遍历所有从城市 x 出发的边
        for (int i = h[x]; i; i = nxt[i]) {
            if (!vis[to[i]] && dis[to[i]] > dis[x] + w[i]) {
                dis[to[i]] = dis[x] + w[i];  // 更新最短距离
                q.push({-dis[to[i]], to[i]});  // 将新的最短距离加入队列
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;  // 输入城市数，航线数和最大免费次数
    cin >> s >> t;  // 输入起点和终点城市编号
    
    // 读取每一条航线，并处理
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;  // 读取航线的起点、终点和价格
        
        // 复制航线到 k 层
        for (int i = 1; i <= k; i++) {
            // 正常航线（收费）
            addedge(a + i * n, b + i * n, c);
            addedge(b + i * n, a + i * n, c);
            
            // 免费航线（费用为 0）
            addedge(a + (i - 1) * n, b + i * n, 0);
            addedge(b + (i - 1) * n, a + i * n, 0);            
        }
    }
    
    // 执行 Dijkstra 算法求解最短路径
    dijkstra();
    
    // 查找从 s 到 t 最少花费的答案
    int ans = inf;
    for (int i = 0; i <= k; i++) {
        ans = min(ans, dis[t + i * n]);  // 查找不同免费次数下的最短路径
    }
    
    cout << ans;  // 输出结果
    return 0;
}