#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

priority_queue<pair<int,int> >q;

int const maxn=2e5+,maxm=;

int n,m,k,s,t,head[maxn],ct,dis[maxn];

bool vis[maxn];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[maxm<<];

void add(int x,int y,int z)

{

    edge[++ct]=N(y,head[x],z); head[x]=ct;

    edge[++ct]=N(x,head[y],z); head[y]=ct;

    for(int i=;i<=k-;i++)

    {

        int u=x+i*n,v=y+(i+)*n;

        edge[++ct]=N(v,head[u],); head[u]=ct;

        u=y+i*n,v=x+(i+)*n;

        edge[++ct]=N(v,head[u],); head[u]=ct;

        u=x+(i+)*n,v=y+(i+)*n;

        edge[++ct]=N(v,head[u],z); head[u]=ct;

        edge[++ct]=N(u,head[v],z); head[v]=ct;

    }

}

void dijkstra()

{

    memset(dis,0x3f,sizeof dis);

    dis[s]=; q.push(make_pair(,s));

    while(q.size())

    {

        int x=q.top().second; q.pop();

        while(vis[x]&&q.size())x=q.top().second,q.pop();

        if(vis[x])break; vis[x]=;

        for(int i=head[x];i;i=edge[i].next)

        {

            int u=edge[i].to;

            if(dis[u]>dis[x]+edge[i].w)

            {

                dis[u]=dis[x]+edge[i].w;

                q.push(make_pair(-dis[u],u));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);

    t+=k*n;

    for(int i=,x,y,z;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    dijkstra();

    printf("%d",dis[t]);

    return ;

}