#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1e6+10;
const int M=1e4+10;
const int Small=1e-8;
int n,m,k;
struct Node{
	int to;
	int next;
	int a;
}e[N];
int head[N];
int pd[N];
int dp[M][M];
int up(double x){
	int xx=x;
	if(x==xx) return xx;
	return xx+1;
}
void dij(){
	memset(dp,0x7f,sizeof(dp));
	int minj=1;
	int minn;
	pd[minj]=true;
	dp[1][0]=0;
	for(int i=1;i<=n;i++){
		for(int kk=0;kk<k;kk++){
			for(int j=head[minj];j;j=e[j].next){
				if(dp[minj][kk]+1>=e[i].a){
					dp[e[i].to][(kk+1)%k]=min(dp[e[i].to][(kk+1)%k],dp[minj][kk]+1);
				}else{
					int kkk=up((e[i].a-dp[minj][kk])/(k+0.0));
					dp[e[i].to][(kk+kkk*k)%k]=min(dp[e[i].to][(kk+kkk*k)%k],dp[minj][kk]+kk*k+kk);
				}
			}
			minn=0x7fffffff;
			pd[minj]=true;
			for(int j=head[minj];j;j=e[j].next){
				if(!pd[j]&&dp[e[i].to][kk]<minn){
					minn=dp[e[i].to][kk];
					minj=e[i].to;
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u,v,a;
		cin>>u>>v>>a;
		e[++cnt].next=head[u];
		head[u]=cnt;
		e[cnt].to=v;
		e[cnt].a=a; 
	}
	dij();
	if(dp[n][0]==2139062143){
		cout<<-1;
	}else
	cout<<dp[n][0];
	return 0; 
}