#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=20005,M=105;
int n,m,k,dis[N][M];
bool f[N][M];
vector<pii>vt[N];
priority_queue<pii,vector<pii>,greater<pii> >q;
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	dis[1][0]=0;
	q.push({1,0});
	while(q.size())
	{
		int u=q.top().first,p=q.top().second;
		q.pop();
		if(f[u][p%k])	continue;
		f[u][p%k]=1;
		for(auto i:vt[u])
		{
			int v=i.first,w=i.second,t;
			if(p>=w)	t=p+1;
			else	t=((w-p+k-1)/k)*k+p+1;
			if(dis[v][t%k]>t)
			{
				dis[v][t%k]=t;
				q.push({v,t});
			}	
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		vt[u].push_back({v,w});
	}
	dijkstra();
	if(!f[n][0])	cout<<"-1\n";
	else	cout<<dis[n][0];
	return 0;
}