#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t,num,away;
int to[2500000],val[2500000],nxt[2500000];
int hea[150000],dis[150000];
bool f[150000];
priority_queue<pair<int,int> >q;
void Dijkstra()
{
    dis[s]=0;q.push(make_pair(0,s));
    while(q.size())
    {
        int u=q.top().second;q.pop();
        if(f[u]) continue;
        f[u]=1;
        for(int i=hea[u];i!=away;i=nxt[i])
        {
            int x=to[i];
            if(dis[u]+val[i]<dis[x])
            {
                dis[x]=dis[u]+val[i];
                q.push(make_pair(-dis[x],x));
            }
        }
    }
}
void Add(int x,int y,int v)
{
    num++;
    to[num]=y;
    val[num]=v;
    nxt[num]=hea[x];
    hea[x]=num;
}
int main()
{
    //freopen("P4568.in","r",stdin);
    //freopen("P4568.out","w",stdout);
    for(int K=1;K<=1;K++)
    {
        cin>>n>>m>>k;
        cin>>s>>t;
        num=0;
        away=n*(k+1);
        for(int i=0;i<n*(k+1);i++) {dis[i]=0x7fffffff;hea[i]=away;f[i]=0;}
        dis[away]=0x7fffffff;
        for(int i=1;i<=m;i++)
        {
            int x,y,v;
            cin>>x>>y>>v;
            for(int j=0;j<=k;j++)
            {
                Add(x+j*n,y+j*n,v);Add(y+j*n,x+j*n,v);
                if(j!=k){Add(x+j*n,y+j*n+n,0);Add(y+j*n,x+j*n+n,0);}
            }
        }
        Dijkstra();
        int ans=0x7fffffff;
        for(int i=0;i<=k;i++) ans=min(ans,dis[t+i*n]);
        cout<<ans;
    }
    return 0;
}