#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,M=2e4+5;
int head[N],tot;
struct{int to,w,nxt;}edge[M];
void addedge(int u,int v,int w)
{
	edge[++tot]={v,w,head[u]};
	head[u]=tot;
}
int n,m,k;
int dis[N][105];
bool check(int mid)
{
	for(int i=1;i<=n;++i)
		for(int j=0;j<k;++j)
			dis[i][j]=-1;
	queue<int>q;
	dis[n][0]=mid;
	q.emplace(n);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int sb=head[u];sb;sb=edge[sb].nxt)
		{
			int v=edge[sb].to,Min=edge[sb].w,upd=0;
			for(int i=0;i<k;++i)
			{
				if(dis[u][i]-1>dis[v][(i-1+k)%k]&&dis[u][i]>=Min)
					upd=1,dis[v][(i-1+k)%k]=dis[u][i]-1;
			}
			if(upd)
				q.emplace(v);
		}
	}
	return dis[1][0]>=0; 
}
signed main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		addedge(v,u,w);
	}
	int l=-1,r=1e6+1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(check(mid*k))
			r=mid;
		else
			l=mid;
	}
	cout<<r*k;
}