#include"iostream"
#include"cstdio"
#include"string"
#define M 1001 
#define inf 1000000009 
using namespace std;
int map[M][M];
int dis[M][M];
int visite[M];
int kth_path(int s,int t,int k,int n)
{
	int i,j,v;
	dis[s][0]=0;
	dis[0][0]=inf; 
	while(1)
	{
		//cout<<"sf"<<endl;
		v=0;  
		for(i=1;i<=n;i++)
		   if(visite[i]<k&&dis[i][visite[i]]<dis[v][0])
		      v=i; 
		if(v==0)
	    	break; 
		if(v==t&&visite[t]==k-1) 
		    break;
		for(i=1;i<=n;i++)
		{
			if(visite[i]<k&&dis[v][visite[v]]+map[v][i]<dis[i][k]) 
			 {
					dis[i][k]=dis[v][visite[v]]+map[v][i]; 
					for(j=k;j>0;j--)
					if(dis[i][j]<dis[i][j-1])
					 {
							int temp=dis[i][j];
							dis[i][j]=dis[i][j-1];
							dis[i][j-1]=temp; 
					 }  
			 } 
		} 
		visite[v]++; 
	} 
	if(dis[t][k-1]<inf)
	  return dis[t][k-1];
	return -1; 
	 
} 
int main()
{
	int n,m;
	int a,b,c;
	int s,t,k; 
	int i,j; 
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
	   visite[i]=0; 
	   for(j=1;j<=M;j++)
	   {
		 map[i][j]=inf; 
		 dis[i][j]=inf;
	   }
	 } 
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(map[a][b]>c)
			map[a][b]=c; 
	} 
	scanf("%d%d%d",&s,&t,&k);
	if(s==t)
	  ++k; 
	printf("%d\n",kth_path(s,t,k,n));
	//system("pause"); 
	return 0; 
}