#include<bits/stdc++.h>
using namespace std;
int n,s,t,p,k,h[5010],maxx,tot,vis[5010],d1[5010],d2[5010],minx=1000001,m,sp[100010][4];
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;
    cin>>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-1;i++){
        d1[i]=minx;
        d2[i]=minx;
    }
    spfa1();
    spfa2();
    int ans=INT_MAX;
    if(k==1){
       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]];
        }
        if(d1[sp[i][2]]+d2[sp[i][1]]<ans){
            ans=d1[sp[i][2]]+d2[sp[i][1]];
        }
       } 
       cout<<ans;
       return 0;
    }
    cout<<d1[t];
    return 0;
}