#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+5;
int n,m,k,head[maxn],dp[100][maxn],vis[100][maxn],cnt;
struct edge{
	int v,tim,nxt;
}e[maxn*2];
void add(int u,int v,int tim){
	e[++cnt].nxt=head[u];
	e[cnt].v=v;
	e[cnt].tim=tim;
	head[u]=cnt;
}
struct node{
	int v,t;
	bool operator<(const node &A)const{
		return t>A.t;
	}
};
priority_queue<node> q;
void dij(){
	memset(dp,127,sizeof(dp));
	dp[0][1]=0;
	q.push(node{1,0});
	while(!q.empty()){
		int u=q.top().v,t=q.top().t;
		q.pop();
		if(vis[t%k][u]) continue;
		vis[t%k][u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,tim=e[i].tim;
			if(t>=tim){
				if(t+1<dp[(t+1)%k][v]){
					dp[(t+1)%k][v]=t+1;
					q.push(node{v,dp[(t+1)%k][v]});
				}
			}else{
				int l=t;
				while(l<tim) l+=k;
				if(l+1<dp[(l+1)%k][v]){
					dp[(l+1)%k][v]=l+1;
					q.push(node{v,dp[(l+1)%k][v]});
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,tim;
		cin>>u>>v>>tim;
		add(u,v,tim);
		add(v,u,tim);
	}
	dij();
	if(vis[0][n]) cout<<dp[0][n]<<endl;
	else cout<<-1<<endl; 
	return 0;
}

15分。

谢谢各位