#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int d[N],e[N],ne[N],maxn=-1000,ans=0x3f3f3f3f,idx,h[N],a[N],n,m,k,st[N][N];
void add(int aa,int b,int c)
{
	e[idx]=b;
	a[idx]=c;
	ne[idx]=h[aa];
	h[aa]=idx++;
}
void ddfs(int kk,int u)
{
	if(u==n)
	{
		if(kk%k==0 and ans>kk)
		{
			ans=kk;
			return;	
		}
	}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i],x=a[i];
		if(!st[u][i])
		{
			st[u][i]=1;
			ddfs(kk+1,j);
			st[u][i]=0;
		}
	}
}
int main()
{
//	freopen("bus.in","r",stdin);
//	freopen("bus.out","w",stdout);
	memset(h,-1,sizeof(h));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int u,v,au;
		cin>>u>>v>>au;
		add(u,v,au);
        maxn=max(maxn,au);
	}
	ddfs(0,1);
   // for(int i=0;i<=maxn;i+=k)
    //{
	  //  ddfs(i,1);
    //}
	if(ans==0x3f3f3f3f)cout<<-1;
	else cout<<ans;
	return 0;
}