code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Edge{
    int v,w,to;
}e[5000005];
struct node{
    int d,w;
    friend bool operator>(const node &x,const node &y)
    {
        return x.w>y.w;
    }
};
int n,m,k,s,t,tot;
int d[1000005],head[1000005],vis[10000005];
const int INF=0x3f3f3f3f;
void addedge(int u,int v,int w)
{
    tot++;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].to=head[u];
    head[u]=tot;
}
void dijkstra()
{
    priority_queue<node,vector<node>,greater<node> >q;
    q.push((node){s,0});d[s]=0;
    while(!q.empty())
    {
        node t=q.top();q.pop();
        if(vis[t.d])continue;
        vis[t.d]=1;
        for(int i=head[t.d];i;i=e[i].to)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[t.d]+w&&!vis[v])
            {
                d[v]=d[t.d]+w;
                q.push((node){v,d[v]});
            }
        }
    }
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>k>>s>>t;
    s++;t++;k++;
    for(int i=1;i<=n*k;i++)
    d[i]=INF;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        u++;v++;
        for(int j=0;j<k;j++)
        {
            int bz=j*n;
            addedge(u+bz,v+bz,w);
            if(j!=k-1)
                addedge(u+bz,v+bz+n,0);
        }
    }
    dijkstra();
    int ans=INT_MAX;
    for(int i=0;i<=k;i++)
    ans=min(ans,d[t+n*i]);
    cout<<ans;
    return 0;
}