C++ :

#include<bits/stdc++.h>
using namespace std;
int n,m,k,u,v,a;
struct node{
	int poi,val;
};
int f[10005][105];
vector<node> e[10005];
bool check(int now)
{
	memset(f,-1,sizeof(f));
	queue<node> q;
	q.push((node){1,k*now}),f[1][0]=k*now;
	while(!q.empty())
	{
		int p=(q.front()).poi,t=(q.front()).val;
		q.pop();
		if(p==n&&t%k==0)
			return true;
		int siz=e[p].size();
		for(int i=0;i<siz;i++)
		{
			int nxt=e[p][i].poi;
			if(e[p][i].val<=t)
			{
				if(f[nxt][(t+1)%k]>t+1||f[nxt][(t+1)%k]==-1)
					q.push((node){nxt,t+1}),f[nxt][(t+1)%k]=t+1;
			}
		}
	}
	return false;
}
int ans(int now)
{
	memset(f,-1,sizeof(f));
	queue<node> q;
	q.push((node){1,k*now});f[1][0]=k*now;
	while(!q.empty())
	{
		int p=(q.front()).poi,t=(q.front()).val;
		q.pop();
		if(p==n&&t%k==0)
			return t;
		int siz=e[p].size();
		for(int i=0;i<siz;i++)
		{
			int nxt=e[p][i].poi;
			if(e[p][i].val<=t)
			{
				if(f[nxt][(t+1)%k]>t+1||f[nxt][(t+1)%k]==-1)
					q.push((node){nxt,t+1}),f[nxt][(t+1)%k]=t+1;
			}
		}
	}
	return -1;
}
int main()
{
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	int maxn=0;
	cin>>n>>m>>k;
	while(m--)
	{
		cin>>u>>v>>a;
		e[u].push_back((node){v,a});
		maxn=max(maxn,a);
	}
	int l=0,r=maxn/k+(maxn%k!=0),hhz=0;
	if(!check(r))
	{
		cout<<-1;
		return 0;
	}
	while(l<=r)
	{
		int mid=l+(r-l)/2;
		if(check(mid))
			hhz=mid,r=mid-1;
		else
			l=mid+1;
	}
	cout<<ans(hhz);
	return 0;
}