rt

#include<bits/stdc++.h>
#define maxn 2100010
using namespace std;
int n,m,k,s,t;
int cnt,head[maxn];
struct line{int to,pre,w;}b[maxn];
struct node{
    int dis,id;
    bool operator<(const node &a)const{
        return dis>a.dis;
    }
};
int dis[maxn],vis[maxn];
void ad(int x,int y,int z)
{
    cnt++;
    b[cnt].to=y;
    b[cnt].pre=head[x];
    b[cnt].w=z;
    head[x]=cnt;
}
void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<node>q;
    dis[s]=0;
    q.push({0,s});
    while(!q.empty())
    {
        int x=q.top().id; q.pop();
        if(vis[x])continue;
        vis[x]=1;
        //printf("x=%d dis=%d\n",x,dis[x]);
        for(int i=head[x];i;i=b[i].pre)
        {
            int y=b[i].to;
            //printf("y=%d dis=%d\n",y,dis[y]);
            if(dis[y]>dis[x]+b[i].w)
            {
                dis[y]=dis[x]+b[i].w;
                q.push({dis[y],y});
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k>>s>>t;
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        ad(x,y,z);
        ad(y,x,z);
        for(int j=1;j<=k;++j)
        {
            ad(x+(j-1)*n,y+j*n,0);//免费边向下一层连边，是层间边
            ad(y+(j-1)*n,x+j*n,0);
            ad(x+j*n,y+j*n,z);//维护下一层的层内边，每一层的图都是一样的
            ad(y+j*n,x+j*n,z);
            //可以存在k条免费边，就有共k+1层图
        }
    }
    dijkstra();
    cout<<dis[t+k*n]<<endl;
    //免费边不是双向的，一但要使用免费边，就一定会往下一层跑，所以等效终点在最底层
	return 0;
}