#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5,MAXK=105;
int n,m,k,ans=-1;
vector<pair<int,int>> G[MAXN];
int vis[MAXN][MAXK];
bool check(int a,int b,int na,int nb,int x){
	if (vis[a][b]-1<x || vis[na][nb]!=-1){
		return false;
	}
	return true;
}
bool bfs(int x){
	queue<pair<int,int>> q;
	q.push({n,0});
	memset(vis,-1,sizeof(vis));
	vis[n][0]=x*k;
	while (!q.empty()){
		pair<int,int> temp=q.front();
		q.pop();
		int a=temp.first,b=temp.second;
		if (vis[a][b]!=0){
			for(int i=0;i<G[a].size();++i){
				pair<int,int> _t=G[a][i];
				int na=_t.first,nb=(b+k-1)%k;
				if (!check(a,b,na,nb,_t.second)) continue;
				vis[na][nb]=vis[a][b]-1;q.push({na,nb});
			}		
		}
	}
	if (vis[1][0]==-1){
		return false;
	}
	return true;
}
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1,u,v,a;i<=m;++i){
		scanf("%d %d %d",&u,&v,&a);
		G[v].push_back({u,a});
	}
	int l=0,r=200000/k;
	while (l<r){
		int mid=(l+r)/2;
		if (bfs(mid)){
			ans=mid*k;r=mid;continue;
		}
		l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}