#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair <int,int>;
int n, m, k, s, t, ans, d[10000][11], st[10000][11];
vector <vector<pii>> e(10000);
set <pair<int,pii>> q;
void dijkstra()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            d[i][j] = 1e9;
    d[s][0] = 0;
    q.insert({0,{s,0}});//插入(值,(编号，使用次数))
    while(q.size())
    {
        auto top = *q.begin();//每次取出最小的，用最优的更新
        q.erase(q.begin());
        int u = top.second.first, cnt = top.second.second;//当前的编号和使用次数
        st[u][cnt] = 1;//当前的值已经确定
        for(auto son:e[u])//更新儿子的状态
        {
            int v = son.first, w = son.second;
            //考虑不用免费次数
            if(!st[v][cnt] && d[v][cnt] > d[u][cnt]+ w)
            {
                d[v][cnt] = d[u][cnt] + w;
                q.insert({d[v][cnt],{v,cnt}});
            }
            //考虑用一次免费次数
            if(cnt+1<=k && !st[v][cnt+1] && d[v][cnt+1] > d[u][cnt])
            {
                d[v][cnt+1] = d[u][cnt];
                q.insert({d[v][cnt+1],{v,cnt+1}});
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k>>s>>t;
    for(int i=1,a,b,w;i<=m;i++)//建图
    {
        cin>>a>>b>>w;
        e[a].emplace_back(make_pair(b,w));
    }
    dijkstra();
    ans = 1e9;
    for(int i=0;i<=k;i++) ans = min(ans,d[t][i]);
    cout<<ans;
    return 0;
}
/*
1.d[i][j]:表示从s到i号点，用了j次免费的最小花费
2.d[i][j] = min(d[i][j], d[k][j-1], d[k][j] + w[k][i]); k -> i
3.ans = min(d[t][i]) i∈[0,k]
4.d[s][0] = 0, else d[i][j] = INF
*/