#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<climits>
#include<cfloat>
using namespace std;
const long long N=1e4+10;
const long long KK=110;
const long long Max=LONG_LONG_MAX/10;
long long n,m,k;
struct Node{
	long long next;
	long long to;
	long long a;
}e[N*2]; 
long long head[N*2];
struct sss{
	long long minj,K,s;
	sss() {}
	sss(long long a,long long b,long long c){
		minj=a;
		K=b;
		s=c;
	}
	bool operator < (sss ab) const{
		return ab.minj<minj;
		//小根堆
		//return minj<a,minj
		//大根对 
	}
};
priority_queue<sss>que;
long long dp[N][KK];
long long pd[N][KK];
void init(){
	cin>>n>>m>>k;
	long long cnt=0;
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		cin>>u>>v>>w; 
		e[++cnt].next=head[u];
		head[u]=cnt;
		e[cnt].to=v;
		e[cnt].a=w;
	}
}
void dij(){
	for(long long i=1;i<=n;i++){
		for(long long j=0;j<=k;j++){
			dp[i][j]=Max;
		}
	} 
	dp[1][0]=0;
	que.push(sss(1,0,0));
	while(!que.empty()){
		long long minj,K,s;
		minj=que.top().minj;
		K=que.top().K;
		s=que.top().s;
		que.pop();
		if(pd[minj][K]) continue;
		pd[minj][K]=true;
		for(long long i=head[minj];i;i=e[i].next){
			if(dp[minj][K]>=e[i].a){
				if(dp[e[i].to][(K+1)%k]>dp[minj][K]+1){
					dp[e[i].to][(K+1)%k]=dp[minj][K]+1;
					que.push(sss(e[i].to,(K+1)%k,dp[e[i].to][(K+1)%k]));
				}
			}else{
				long long kkk=ceil((e[i].a-dp[minj][K]+0.0)/(k+0.0));
				if(dp[e[i].to][(K+1)%k]>dp[minj][K]+kkk*k+1){
					dp[e[i].to][(K+1)%k]=dp[minj][K]+kkk*k+1;
					que.push(sss(e[i].to,(K+1)%k,dp[e[i].to][(K+1)%k]));
				}
			}
		}
	}
}
int main(){
	init();
	dij();
	if(dp[n][0]==Max){
		cout<<-1;
	}else{
		cout<<dp[n][0];
	}
	return 0;
}