求调，wa第8,9,10

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define endl '\n'
using namespace std;
const int N=1e4+10,K=105;
struct Node{
	int to,w;
};
struct node{
	int u,t;
};
int n,m,k,dis[N][K],vis[N][K];
vector<Node> g[N];
queue<node> q;
int cal(int x,int y){
	if(x>=y) return x;
	else return x+ceil(1.0*(y-x)/k)*k; 
}
void spfa(){
//	cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++) dis[i][j]=1e18;
	}
	dis[1][0]=0,q.push({1,0}),vis[1][0]=1;
	while(!q.empty()){
		int u=q.front().u,t=q.front().t;
		q.pop();
//		cout<<u<<' '<<t<<' '<<dis[u][t]<<endl;
		vis[u][t]=0;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].to,w=g[u][i].w;
			if(cal(dis[u][t]+1,w)<dis[v][(t+1)%k]){
				dis[v][(t+1)%k]=cal(dis[u][t]+1,w);
				if(!vis[v][(t+1)%k]) vis[v][(t+1)%k]=1,q.push({v,(t+1)%k});
			}
		} 
	}
	if(dis[n][0]==1e18) cout<<-1<<endl;
	else cout<<dis[n][0]<<endl; 
}
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	spfa();
	return 0;
}