////V1 35分 暴力改BFS找最短路，注意环路+时间限制 
//#include<bits/stdc++.h>
//using namespace std;
//const int maxn=1E4+10;
//int n,m,k,u,v_,a,ans,vis[maxn][110];
//struct road{
//	int to,a;
//};
//struct step{
//	int id,time;
//};
//vector<road> v[maxn];
//queue<step> q;
//int main(){
//	cin>>n>>m>>k;
//	for(int i=0;i<m;i++){
//		cin>>u>>v_>>a;
//		v[u].push_back(road{v_,a});//单向通路 
//	}
//	q.push(step{1, 0});
//	vis[1][0]=true;
//	while(q.size()){//最短路，改造BFS模板 
//		step t=q.front();
//		q.pop();
//		if(t.id==n && t.time%k==0){//到达即找到最短路，本题特判到达时间是K倍数 
//			cout<<t.time;
//			return 0;
//		}
//		for(int i=0;i<v[t.id].size();i++){
//			int d=v[t.id][i].to, ti=t.time+1;
//			if(vis[d][ti%k])	continue;//防止重复访问陷入死循环 
//			//注意本题可能有环！！！而且本题最短路有时间点要求！！！所以设置特殊vis 
//			q.push(step{d, ti});
//			vis[d][ti%k]=true;
//		} 
//	}
//	cout<<"-1";//没有符合要求的到达终点的路 
//	return 0;
//} 

////V2 50分 加入道路开放时间的讨论，跟上面比只加了三行if(v[t.id][i].a>ti){//道路开放时间没到 
//#include<bits/stdc++.h>
//using namespace std;
//const int maxn=1E4+10;
//int n,m,k,u,v_,a,ans,vis[maxn][110];
//struct road{
//	int to,a;
//};
//struct step{
//	int id,time;
//};
//vector<road> v[maxn];
//queue<step> q;
//int main(){
//	cin>>n>>m>>k;
//	for(int i=0;i<m;i++){
//		cin>>u>>v_>>a;
//		v[u].push_back(road{v_,a});//单向通路 
//	}
//	q.push(step{1, 0});//起点 
//	vis[1][0]=true;
//	while(q.size()){//最短路，改造BFS模板 
//		step t=q.front();
//		q.pop();
//		if(t.id==n && t.time%k==0){//到达即找到最短路，本题特判到达时间是K倍数 
//			cout<<t.time;
//			return 0;
//		}
//		for(int i=0;i<v[t.id].size();i++){
//			int d=v[t.id][i].to, ti=t.time+1;
//			if(vis[d][ti%k])	continue;//防止重复访问陷入死循环 
//			//注意本题可能有环！！！而且本题最短路有时间点要求！！！所以设置特殊vis 
//			if(v[t.id][i].a>ti){//道路开放时间没到，默认这个节点晚wait时间进园子即可
//				int wait=((v[t.id][i].a-ti)/k+1)*k;
//				ti+=wait;
//			}
//			q.push(step{d, ti});
//			vis[d][ti%k]=true;
//		} 
//	}
//	
//	cout<<"-1";//没有符合要求的到达终点的路 
//	return 0;
//} 

/*
思考一下不能AC的问题可能出在哪里？出在不确定的等待时间，把push进queue的各个Step的时间顺序弄乱了（可能早到某地点的时间其实更晚）。

        比如我们在某个时间time1走到了某个地点i，这种状态没有vis过，所以第26行往下走， 并赋值vis[i][time1 % k] = true，经过之后的若干步，最终这条路走通了，即走到n，且时间正好是k的整数倍，然后取得了一个ans。稍晚之后，我们通过另一条路，花费更少的时间time2（time2<time1）也走到了地点i，不走运的是，虽然time2<time1，但恰好time2 % k == time1 % k（这完全有可能！），而此时vis[i][time1%k]已经为true了，因此第26行就不再往下走了，而原本小Z可以以更早的时间离开景区的（如果按time2往下走的话，因为time2%k==time1%k，只要time1走得通，time2一定也走得通，而time2<time1，只是由于它push进队列比较晚，被排在后面了）。

        那么怎么办？我们有什么办法让time2，比time1提前被我们拿出来用。Bingo！当然要想到用优先队列priority_queue，只需要对到达时间进行排序，那么从队列中取出队首元素的时候，总是取时间最早的数据。OK，让我们对Step结构体进行从大到小排序，并把queue改成priority_queue，其他不做变动：
*/ 

//V3 100分 加入道路开放时间的讨论，用priority_queue 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1E4+10;
int n,m,k,u,v_,a,vis[maxn][110];
struct road{
	int to,a;
};
struct step{
	int id,time;
	bool operator < (const step& t) const{
		return time > t.time;//改priority_queue可以按到达时间排序 ,默认是小顶堆，所以重载< 改成大顶堆 
	}
};
vector<road> v[maxn];
priority_queue<step> q;
int main(){
//	freopen("P9751_21.in", "r", stdin);
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		cin>>u>>v_>>a;
		v[u].push_back(road{v_,a});
	}
	q.push(step{1, 0});
	while(q.size()){ 
		step t=q.top();
		q.pop();
		if(t.id==n && t.time%k==0){//仍然是到达即找到最短路，本题特判到达时间是K倍数（0也算） 
			cout<<t.time;
			return 0;
		}
		if(vis[t.id][t.time%k])	continue;
		//按时间先访问的元素先vis标记。如果在for循环里就判断，由于wait等待时间差异，可能先到达的反而先因为后到达的vis排除 
		vis[t.id][t.time%k]=true; 
		for(int i=0;i<v[t.id].size();i++){
			int d=v[t.id][i].to, ti=t.time+1;
			if(v[t.id][i].a>=ti){//要取=，这个临界点还没开放道路  
				int wait=((v[t.id][i].a-ti)/k+1)*k;
				ti+=wait;
			} 
			q.push(step{d, ti});
		} 
	}
	
	cout<<"-1";
	return 0;
} 
/*
input1
9 15 97
1 1 990149
6 4 393083
4 7 171280
6 7 635660
8 6 123113
1 2 384925
6 7 507533
8 6 416969
3 4 975110
2 5 575466
2 4 72458
7 9 923003
5 3 590414
4 8 733761
7 5 440313

output1
923052

input2
5 5 1
1 2 0
2 3 0
3 4 0
4 5 0
1 5 1

output2
2
*/

//另一种写法，仅仅是改变结构体，将time分成wait和dis记录，便于向难题扩展 
//#include<bits/stdc++.h>
//using namespace std;
//const int maxn=1E4+10;
//int n,m,k,u,v_,a,vis[maxn][110];
//struct road{
//	int to,a;
//};
//struct step{
//	int id,wait,dis;
//	bool operator < (const step& t) const{
//		return wait+dis > t.wait+t.dis;//记录门口等待时间wait和路上距离时间dis，题目对进入离开时间都有要求 
//	}
//};
//vector<road> v[maxn];
//priority_queue<step> q;
//int main(){
//	freopen("P9751_21.in", "r", stdin);
//	cin>>n>>m>>k;
//	for(int i=0;i<m;i++){
//		cin>>u>>v_>>a;
//		v[u].push_back(road{v_,a});
//	}
//	q.push(step{1, 0, 0});
//	while(q.size()){ 
//		step t=q.top();
//		q.pop();
//		if(t.id==n && t.dis%k==0){//题意是保证进入时间wait和离开时间wait+dis都要是k倍数，所以保证wait和dis是k倍数即可
//			cout<<t.wait + t.dis;
//			return 0;
//		}
//		if(vis[t.id][t.dis%k])	continue;
//		//按时间先访问的元素先vis标记。如果在for循环里就判断，由于wait等待时间差异，可能先到达的反而先因为后到达的vis排除 
//		vis[t.id][t.dis%k]=true; 
//		for(int i=0;i<v[t.id].size();i++){
//			int d=v[t.id][i].to, time=t.wait+t.dis+1, wait=t.wait, dis=t.dis+1;
//			if(v[t.id][i].a>=time){//要取=，这个临界点还没开放道路 
//				int need=((v[t.id][i].a-time)/k+1)*k;
//				wait+=need;//保证wait一直是k的倍数 
//			} 
//			q.push(step{d, wait, dis});
//		} 
//	}
//	
//	cout<<"-1";
//	return 0;
//}