玄关，求条

#include<bits/stdc++.h>
using namespace std;
vector<int> a[10000];
pair<int,int> f[10000];
int x[10000];
int n,m,k,c,y,ma=-2e9,ans=2e9;
int dfs(int p,int s)
{
	if(p==m&&s%k==0)
		return s;
	else if(p==m)
		return 0x3f3f3f3f;
	if(f[p].first!=-1&&f[p].second==s)
		return f[p].first;
	int mi=1e9;
	for(int i=0;i<a[p].size();i++)
		if(x[a[p][i]]>=s)
			mi=min(mi,dfs(a[p][i],s+1));
	f[p].first=mi;
	f[p].second=s;
	return mi;
}
int main()
{
	memset(f,-1,sizeof(f));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",c,y,x[i]);
		--y;
		--c;
		a[c].push_back(y);
		a[y].push_back(c);
		ma=max(ma,x[i]);
	}
	for(int i=0;i<=ma;i+=k)
		ans=min(ans,dfs(0,i));
	printf("%d",ans);
}