#include<bits/stdc++.h>

using namespace std;

int n,p,k,h[5010],maxx,tot,vis[5010],d1[5010],d2[5010],m,sp[100010][4],ans = 1e9, s, t;
struct m
{
    int ver,nx,ed;
}e[200010];
void add(int x,int y,int z)
{
    e[++tot].ver=y,e[tot].nx=h[x],e[tot].ed=z,h[x]=tot;
}
void spfa1()
{
       memset(vis,0,sizeof(vis));
        queue <int> a;
        a.push(s),vis[s]=1,d1[s]=0;
        while(!a.empty())
        {
            int x=a.front();
            a.pop();
            vis[x]=0;
            for(int i=h[x];i;i=e[i].nx)
            {
                int y=e[i].ver;
                int z=e[i].ed;
                if(d1[x]+z<d1[y])
                {
                    
                    d1[y]=d1[x]+z;
                    if(!vis[y])vis[y]=1,a.push(y);
                }
            }
       }
}
void spfa2()
{
       memset(vis,0,sizeof(vis));
        queue <int> a;
        a.push(t),vis[t]=1,d2[t]=0;
        while(!a.empty())
        {
            int x=a.front();
            a.pop();
            vis[x]=0;
            for(int i=h[x];i;i=e[i].nx)
            {
                int y=e[i].ver;
                int z=e[i].ed;
                if(d2[x]+z<d2[y])
                {
                    
                    d2[y]=d2[x]+z;
                    if(!vis[y])vis[y]=1,a.push(y);
                }
            }
       }
}
int main()
{
    freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
    cin >> n >> m >> k >> s >> t;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
        sp[i][1]=x,sp[i][2]=y,sp[i][3]=z;
    }
    for(int i=0;i<=n;i++)
    {
        d1[i]=1e9;
        d2[i]=1e9;
    }
    spfa1();
    spfa2();
    //d2[s] = d1[t];
    if(k == 0)
    {
        cout << d1[t];
        return 0;
    }
    for(int i=1;i<=m;i++)
        if(d1[sp[i][1]]+d2[sp[i][2]]<ans)
            ans=d1[sp[i][1]]+d2[sp[i][2]];
    for(int i=1;i<=m;i++)
        if(d1[sp[i][2]]+d2[sp[i][1]]<ans)
            ans=d1[sp[i][2]]+d2[sp[i][1]];
    
        
    cout<<ans;
    return 0;
}