rt

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int ans[10001][101];
bool bj[10001][101];
int read(int &x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
}
//--------------------------------------图 
struct Node{
	int to,w;
};
vector <Node> a[20001];
//--------------------------------------堆 
struct Node2{
	int now,w;
};
Node2 b[100000];
int tot=0;
void work(int x){
	if(x/2>=1&&b[x].w<b[x/2].w){
		swap(b[x],b[x/2]);
		work(x/2);
	}
}
void work1(int x){
	if(b[x*2].w<b[x*2+1].w&&x*2+1<=tot&&b[x*2].w<b[x].w){
		swap(b[x*2],b[x]);
		work1(x*2);
	}
	else if(x*2+1<=tot&&b[x*2+1].w<b[x].w){
		swap(b[x*2+1],b[x]);
		work1(x*2+1);
	}
	else if(x*2+1>tot&&x*2<=tot&&b[x*2].w<b[x].w){
		swap(b[x*2],b[x]);
		work1(x*2);
	}
	else{
		return;
	}
}
//----------------------------------------------------bfs
void bfs(int x,int js){
	if(bj[x][js%k+1]){
		return;
	}
	bj[x][js%k+1]=1;
	ans[x][js%k+1]=js;
	for(auto it:a[x]){
		b[++tot]={it.to,js+max((it.w-js+k-1)/k,0)*k+1};
		work1(tot);
	}
}
//------------------------------------------------------------
int main(){
	read(n);
	read(m);
	read(k);
	for(int i=1;i<=m;i++){
		int u,v,w;
		read(u);
		read(v);
		read(w);
		a[u].push_back({v,w});
	}
	b[++tot]={1,0};
	ans[n][1]=-1;
	while(tot!=0){
		bfs(b[1].now,b[1].w);
		swap(b[1],b[tot]);
		tot--;
		work1(1);
	}
	cout<<ans[n][1];
	return 0;
}