#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdio>

using std:: endl;
using std:: cin;
using std:: cout;

const int maxn = 5000001;
const int mof = 5e4;
const int INF = 21000000;

int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct data{
    int next;
    int to;
    int w;
}t[maxn];
int head[maxn],js;

inline void add(int u,int v,int w){
    t[++js].next=head[u];
    t[js].w=w;
    t[js].to=v;
    head[u]=js;
}

int n,m,k;
int dis[maxn];
bool flag[maxn];

void dij(int begin){
    std:: priority_queue<std:: pair<int,int>,std:: vector<std:: pair<int,int> >,std:: greater<std:: pair<int,int> > >q;
    dis[begin]=0;
    q.push(std:: make_pair(0,begin));
    while(!q.empty()){
        int u=q.top().second; q.pop();
        if(flag[u]) continue;
        flag[u]=true;
        for(int i=head[u];i;i=t[i].next){
            int v = t[i].to; 
            std:: cerr<<"v:"<<v<<" ";
            if(dis[v]>t[i].w+dis[u]){
                dis[v]=t[i].w+dis[u];
                q.push(std:: make_pair(dis[v],v));
            }
        }
    }   
}
int main(){
    n=read(); m=read(); k=read();
    int begin=read(),end=read();
    std:: cerr<<"end: "<<end<<endl;//debugger , ignore it
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z); add(y,x,z);
        for(int i=1;i<=k;i++){
            add(x+mof*(i-1),y+mof*i,0);//add a edge to next layer
            add(y+mof*(i-1),x+mof*i,0);
            add(x+mof*i,y+mof*i,z);// add a edge in every layer
            add(y+mof*i,x+mof*i,z);
        }
    }
    for(int i=0;i<=n+mof*k;i++) dis[i]=INF;
    dij(begin);
    cout<<dis[end+mof*k];
    return 0;
}