#include<bits/stdc++.h>
#define make(x,y) make_pair(x,y)
#define N 5000006
using namespace std;
const int inf=2e9;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m,s,u,v,w,cnt,pos,minn,dis[N],head[N],K,t;
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct k
{
	int son,val,next;
}k[N];
void add(int a,int b,int c)
{
	cnt++;
	k[cnt].son=b;
	k[cnt].val=c;
	k[cnt].next=head[a];
	head[a]=cnt;
}
void dij()
{
	for(int i=1;i<=n*(K+1);i++)dis[i]=inf;
	dis[s]=0;
	q.push(make(0,s));
	while(!q.empty())
	{
		pos=q.top().second;
		q.pop();
		if(vis[pos]==1)continue;
		vis[pos]=1;
		for(int i=head[pos];i!=0;i=k[i].next)
		{
			if(dis[k[i].son]>dis[pos]+k[i].val)
			{
				dis[k[i].son]=dis[pos]+k[i].val;
				q.push(make(dis[k[i].son],k[i].son));
			}
		}
	}
}
int main()
{
	n=read();m=read();s=read();
	t=read();K=read();
	for(int i=1;i<=m;i++)
	{
		u=read();v=read();w=read();
		for(int j=0;j<=K;j++)
		{
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
			if(j!=K)
			{
				add(u+j*n,v+(j+1)*n,0);
				add(v+j*n,u+(j+1)*n,0);
			}
		}
	}
	dij();
	int ans=inf;
	for(int i=0;i<=K;i++)ans=min(ans,dis[t+i*n]);
	cout<<ans<<"\n";
	return 0;
}