#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int n,m,k,x,y,a,able[N][105];
struct ss{
	int fr,x,d,time;
};
vector<pair<int,int>> v[N];
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>a;
		v[x].push_back({y,a});
	} 
	queue<ss> q;
	memset(able,0x3f,sizeof able);
	q.push({0,1,0,-1});
	for(int i=0;i<k;++i)able[0][i]=-1;
	while(!q.empty()){
		int x=q.front().x,fr=q.front().fr,time=q.front().time,d=q.front().d;
		q.pop(); 
		int t=ceil(1.0*(time-d+1)/k)*k+d;
		if(able[x][d%k]<=max(t,able[fr][(d-1+k)%k])+1)continue;
		able[x][d%k]=max(t,able[fr][(d-1+k)%k]+1);
		for(auto r:v[x]){
			int tm=r.second,c=r.first;
			q.push({x,c,d+1,tm});
		}
	}
	cout<<(able[n][0]==0x3f3f3f3f3f3f3f3f?-1:able[n][0]);
} 

这是本蒟蒻赛时代码，给机房的大佬看都觉得有点问题，但暂时没有被hack，请大佬帮忙hack（如果可以证明是正解可以给我讲一下吗 QAQ）。