CSPJT4

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,K=110;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct node{
	int x,k;
};
int n,m,k,dis[N][K];
vector<int> G[N],e[N];
bool check(int x){
	memset(dis,-1,sizeof(dis));
	dis[n][0]=x*k;
	queue<node>q;
	q.push(node{n,0});
	while(q.size()){
		int u=q.front().x,b=q.front().k;
		q.pop();
		if(dis[u][b]==0) continue;
		for(int i=0;i<G[u].size();i++){
			if(e[x][i]>=dis[x][b]) continue;
			int v=G[u][i],p=(b+k-1)%k;
			if(dis[v][p]!=-1) continue;
			dis[v][p]=dis[u][b]-1;
			q.push(node{v,p});
		}
	}
	if(dis[1][0]==-1) return false;
	return true;
}
int main(){
	ios::sync_with_stdio(false),cout.tie(0);
	n=read(),m=read(),k=read();
	while(m--){
		int u=read(),v=read(),w=read();
		G[v].push_back(u);
		e[v].push_back(w);
	}
	int l=0,r=2e6,ans=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans*k;
	return 0;
}