第二十一个测试点错了，

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
vector<pair<int,int>>a[10010];
int d[10010][110];
void dj(){
	memset(d,0x3f,sizeof(d));
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	q.push({1,0});
	while(!q.empty()){
		auto t=q.top();
		q.pop();
		int t1=t.first;
		int t2=t.second;
		if(d[t1][t2%k]<t2) continue;
		for(int i=0;i<a[t1].size();i++){
			int j=a[t1][i].first;
			int s=t.second;
			if(s+1<a[t1][i].second){
				s+=(a[t1][i].second-t2-1+k)/k*k;
			}
			if(s+1<d[j][(s+1)%k]){
				d[j][(s+1)%k]=s+1;
				q.push({j,s+1});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>k;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back({y,z});
	}
	dj();
	if(d[n][0]>=0x3f3f3f3f3f3f3f3f){
		cout<<"-1";
	}
	else cout<<d[n][0];
	return 0;
}