#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,e;
const int MAXN=605;
int g[MAXN][MAXN];
int u[6005],v[6006],w[6006];
void f(){
	for(int k=0;k<=n-1;k++){
		for(int i=0;i<=n-1;i++){
			for(int j=0;j<=n-1;j++){
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
}
int ans=1e9;
int main(){
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	cin>>n>>m>>k;
	cin>>s>>e;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
	}
	if(k==1){
		for(int i=1;i<=m;i++){
			memset(g,0x3f,sizeof(g));
			for(int j=1;j<=m;j++){
				if(i!=j){
					g[u[j]][v[j]]=g[v[j]][u[j]]=min(g[u[j]][v[j]],w[j]);
				}else g[u[j]][v[j]]=g[v[j]][u[j]]=0;
			}
			f();
			ans=min(ans,g[s][e]);
		}
	}else {
		for(int i=1;i<=m;i++){
			g[u[i]][v[i]]=g[v[i]][u[i]]=min(g[u[i]][v[i]],w[i]);
		}
		f();
		ans=g[s][e];
	}
	cout<<ans<<endl;
	return 0;
}