#include<bits/stdc++.h>
using namespace std;
int n,m,k,e[20004],s,t[20004],ne[20004],h[10004],idx,ans=0x3f3f3f3f;
void add(int a,int b,int c)
{
	e[idx]=b;
	t[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u,int s)
{
	if(u==n and s%k==0)
	{
		ans=min(ans,s);
	} 
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i],w=t[i];
		if(s<w)
		{
			if((w-s)%k==0)
			{
				dfs(j,w+1);
			}
			else
			{
				dfs(j,1+s+(((w-s)/k)+1)*k);
			}
		}
		else
		{
			dfs(j,s+1);
		}
	}
	return ;
}
int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dfs(1,0);
	if(ans==0x3f3f3f3f)cout<<-1;
	else cout<<ans;
	return 0;
}

还有就是打的不是正解方法 请各位大佬找下为什么会MLE