#include
#include
using namespace std;
int map[500][500],dis[500],u[500],v[500],c[500];
int m,n,s,d,w,ans=2147483647; //修改初始化为最大值
void dfs(int ve,int len,int cnt){
if(cnt==w && ve==d){ //修改判断条件
ans=min(len,ans);
return;
}
if(cnt>=w) return; //如果步数超过限制，直接返回
for(int i=1;i<=n;i++){
if(map[ve][i]!=2147483647)
dfs(i,len+map[ve][i],cnt+1);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=2147483647; //修改初始化为最大值
}
}
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>c[i];
map[u[i]][v[i]]=c[i];
}
cin>>s>>d>>w;
if(s==d){
cout<<"0";
return 0;
}
dfs(s,0,0);
if(ans==2147483647) cout<<"2147483647";
else cout<<ans;
return 0;
}
