#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> e[10010];
int n,m,k,dis[10010][111];
bool check(int t){
	for(int i=1;i<=n;i++)for(int j=0;j<k;j++)dis[i][j]=-1;
	dis[n][0]=t;
	queue<pair<int,int>> q;
	q.push(make_pair(n,0));
	while(!q.empty()){
		int u=q.front().first;
		int t=q.front().second;
		q.pop();
		for(auto p:e[u]){
			int v=p.first;
			int w=p.second;
			if(dis[u][t]>w&&dis[v][(t+1)%w]<dis[u][t]-1){
				dis[v][(t+1)%k]=dis[u][t]-1;
				q.push(make_pair(v,(t+1)%k));
			}
		}
	}
	return dis[1][0]>=0;
}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[v].push_back(make_pair(u,w));
	}
	int l=-1,r=3e7/k;
	while(l+1<r){
		int mid=(l+r)/2;
		if(check(mid*k))r=mid;
		else l=mid;
	}
	r*=k;
	if(r>5e6)r=-1;
	cout<<r;
}

运行超时（啊其实是根本运行不出来）求调。