#include<bits/stdc++.h>
#define ll long long
#define mkp make_pair
using namespace std;
ll n,m,k;
vector<pair<ll,ll> > g[20005];
queue<pair<ll,ll> > q;
ll q2[20005],top=1,ans=LONG_LONG_MAX;
bool vis[1000005];
bool check(ll mid)
{
	bool flag=0;
	q.push(make_pair(1,q2[mid]*k));
	while(!q.empty())//普通广搜 
	{
		ll u=q.front().first,t=q.front().second;
		if(u==n&&t%k==0)
		{
			ans=min(ans,t);
			flag=1;//有答案 
			break;
		}
		for(int i=0;i<g[u].size();i++)//拓展到子节点 
			if(t>=g[u][i].second)
				q.push(mkp(g[u][i].first,t+1));
		q.pop();
	}
	return flag;
}
int main()
{
//	freopen("bus.in","r",stdin);
//	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;
	q2[top++]=0;
	vis[0]=1;
	for(int i=1;i<=m;i++)
	{
		ll u,v,a;
		cin>>u>>v>>a;
		g[u].push_back(make_pair(v,a));
		if(!vis[(int)ceil(a*1.0/k)])q2[top++]=((int)ceil(a*1.0/k));//将可能的起始时间放入数组 
		vis[(int)ceil(a*1.0/k)]=1;
	}
	sort(q2+1,q2+top+1);//排序 
	ll l=1,r=top,mid;//二分
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	if(ans==LONG_LONG_MAX)cout<<-1;
	else cout<<ans;
	return 0;
}