子任务1正确，子任务2全错

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
struct edge{
	int v,a;
};
vector<edge> g[N];
int dis[N][100],tme;
int n,m,k,u,v,a;
bool b[N][100];
priority_queue<pair<int,int>> pq;
void dijk(int sta){
	memset(dis,0x3f,sizeof dis);
	dis[sta][0]=0;
	pq.push(make_pair(0,sta));
	while(pq.size()){
		int x=pq.top().second;
		int len=-pq.top().first;
		pq.pop();
		if(!b[x][len%x]){
			b[x][len%x]=true;
			for(int i=0;i<g[x].size();i++){
				int tme=len;
				int y=g[x][i].v;
				int t=g[x][i].a;
				if(tme<t){
					if((t-tme)%k==0){
						tme=t;
					}else{
						tme+=((t-tme)/k+1)*k;
					}
				}
				if(tme+1<dis[y][(tme+1)%k]){
					dis[y][(tme+1)%k]=tme+1;
					pq.push(make_pair(-(tme+1),y));
				}
			}
		}
	}
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>a;
		g[u].push_back((edge){v,a});
	}
	dijk(1);
	int res=dis[n][0];
	if(res==0x3f3f3f3f){
		cout<<-1;
	}else{
		cout<<res;
	}
	return 0;
}