#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m,k,ans;
struct mt{
	int d[130][130];
	mt(){memset(d,0,sizeof(d));}
}mp[100],o,w;
const mt operator *(const mt &a,const mt &b){
	mt c;
	for(int i=0;i<=3*n;i++)
		for(int j=0;j<=3*n;j++)
			for(int l=0;l<=3*n;l++)
				c.d[i][j]+=a.d[i][l]*b.d[l][j];
	return c;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)
		mp[0].d[i][0]=mp[0].d[i][i+n]=mp[0].d[i+n][i+2*n]=1;
	mp[0].d[0][0]=1;
	for(int i=0;i<=3*n;i++)
		o.d[i][i]=1;
	for(int i=1,u,v,w;i<=m;i++)
		scanf("%lld%lld%lld",&u,&v,&w),
		mp[0].d[u+n*(w-1)][v]++;
	int log=1;
	for(;;log++){
		mp[log]=mp[log-1]*mp[log-1];
		w=o*mp[log];
		int res=0;
		for(int j=1;j<=n;j++)
			res+=w.d[j][0]-1;
		if(res>=k)break;
		if(log>=64){
			printf("-1");
			return 0;
		}
	}
	for(;log>=0;log--){
		w=o*mp[log];
		int res=0;
		for(int j=1;j<=n;j++)
			res+=w.d[j][0]-1;
		if(res<k)o=w,ans+=(1ll<<log);
	}
	printf("%lld",ans);
	return 0;
}