样例1能过，样例2卡了

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int N=1e4+10;
int n,m,k,f[N][100],ans;
bool flag;
vector<int> g[N],a[N];
queue<int> q;

inline void add(int u,int v,int x)
{
	g[u].emplace_back(v);
	a[u].emplace_back(x);
	
	return ;
}

int main()
{
//	freopen("bus.in","r",stdin);
//	freopen("my.ans","w",stdout);
	
	scanf("%d%d%d",&n,&m,&k);
//	printf("%d %d %d\n",n,m,k);
	for(int i=1;i<=m;++i)
	{
		int u,v,x;
		scanf("%d%d%d",&u,&v,&x);
//		printf("%d %d %d\n",u,v,x);
		add(u,v,x);
	}
	
	memset(f,INF,sizeof f);
	f[1][0]=0;
	ans=-1;
	q.push(1);
	
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
//		printf("%d:",u);
		
		for(int i=0;i<g[u].size();++i)
		{
			int v=g[u][i];int w=a[u][i];
			
			for(int j=0;j<k;++j)
			{
				if(1+f[u][(j-1+k)%k]<f[v][j])
					f[v][j]=1+f[u][(j-1+k)%k],flag=1;
				
				if(w>f[v][j])
				{
					int t=(w-f[v][j])/k;
					
					f[u][j]+=t*k;
					
					if(w>f[v][j]) f[v][j]+=k;
				}
				
			}
			
			if(flag) q.push(v)/*,printf("%d-%d ",v,w)*/; 
			flag=0;
		}
//		printf("\n");
	}
	
	if(f[n][0]<1061109567) ans=f[n][0];
	
	printf("%d",ans);
	
	return 0;
}