#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=10000+10;
const int M=20000+10;
int n,m,k;
int f[N][100];//记录到达第i个点，时间模k余数为j时的最小时间 
struct node{
	int v,a;//到达 v点这条边的开放时间为 a 
};
vector<node> e[N];
priority_queue<pair<int,int>> q;
int main(){
	cin>>n>>m>>k;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({y,z});
	}
	//f[1][0]:起点出发时最早为0点 
	f[1][0]=0;
	q.push(make_pair(0,1));
	while(q.size()){
		auto temp=q.top();
		//u:当前点。ti:到达当前点的最少时间 
		int u=temp.second,ti=-temp.first;
		q.pop();
		//如果终点有更新 
		if(f[n][0]!=0x3f3f3f3f){
			cout<<f[n][0];
			return 0;
		}
		//枚举u点的所有邻接点 
		for(auto it:e[u]){
			//v:u的邻接点，a:u到v这条边的开放时间 
			int v=it.v,a=it.a;
			//如果已开放 
			if(ti>=a){
				//更新f[v][(ti+1)%k]
				if(ti+1<f[v][(ti+1)%k]){
					f[v][(ti+1)%k]=ti+1;
					q.push(make_pair(-ti-1,v));
				}
			}
			//如果还没开放 
			else{
				//则可以选择假设在出发点等待k的某倍时间
				//t:等待后的当前时间 
				int t=ceil((a-ti)*1.0/k)*k+ti;
				if(t+1<f[v][(t+1)%k]){
					f[v][(t+1)%k]=t+1;
					q.push(make_pair(-t-1,v));
				}
			} 
		}
	}
	cout<<-1;
	return 0;
}