#include<bits/stdc++.h>
using namespace std;
#define rint register int
const int maxn=2e4+5,inf=0x3f3f3f3f;
struct edge{
	int to,nxt,w,lock;
}e[maxn];
struct point{
	int dis[105];
}x[maxn];
struct node{
	int id,dis;
};
inline int read()
{
	int f=1,x=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,m,k,cntedge,head[maxn];
bool vis[maxn][105];
inline void add_edge(int u,int v,int w,int lock)
{
	e[++cntedge]=edge{v,head[u],w,lock};
	head[u]=cntedge;
}
inline int pdis(int now,int lock)
{
	if(now>=lock)return now+1;
	int d=lock-now;
	if(d%k==0)return lock+1;
	return now+(d/k+1)*k+1;
}
//inline void dfs(int u,int tim)
//{
//	for(rint i=head[u];i;i=e[i].nxt)
//	{
//		int v=e[i].to,d=pdis(tim,e[i].lock);
//		if(x[v].dis[d%k]>d)x[v].dis[d%k]=d;
//		if(!vis[v])
//		{
//			vis[v]=1;
//			dfs(v,d);
//			vis[v]=0;
//		}
//	}
//}
inline void bfs()
{
	queue<node>q;
	q.push(node{1,0});
	while(!q.empty())
	{
		node a=q.front();
		q.pop();
		int u=a.id;
		vis[u][a.dis%k]=0;
		for(rint i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to,d=pdis(a.dis,e[i].lock);
			if(x[v].dis[d%k]>d)
			{
				x[v].dis[d%k]=d;
				if(!vis[v][d%k])
				{
					vis[v][d%k]=1;
					q.push(node{v,d});
				}
			}
		}
	}
}
int main()
{
	n=read(),m=read(),k=read();
	for(rint i=1;i<=n;i++)
		for(rint j=0;j<k;j++)
			x[i].dis[j]=inf;
	for(rint i=1;i<=m;i++)
	{
		int u=read(),v=read(),lock=read();
		add_edge(u,v,1,lock);
	}
	bfs();
	if(x[n].dis[0]==inf)return puts("-1"),0;
	printf("%d",x[n].dis[0]);
	return 0;
}

bfs我跑出来是85pts,dfs却只能跑40pts，不只是tle,还有wa~~(Wonderful Answer)~~,为什么呢