#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long dis[10005];
bool vis[10005];
vector<long long>G[10005],ds[10005];
struct node {
  int u,d;
  bool operator>(const node& a)const{ return d>a.d; }
};
priority_queue<node,vector<node>,greater<node> >que;
void dij(){
	for(int i=1;i<=n;i++)dis[i]=1e10;
	que.push({1,0});
	dis[1]=0;
	while(!que.empty()){
		int u=que.top().u;
		que.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			if(max(dis[u]+1,ds[u][i])<dis[G[u][i]]){
				dis[G[u][i]]=max(dis[u]+1,ds[u][i]);
				que.push({G[u][i],dis[G[u][i]]});
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	while(m--){
		int u,v,l;
		cin>>u>>v>>l;
		G[u].push_back(v);
		ds[u].push_back(l);
	}
	dij();
	cout<<((dis[n]+k-1)/k)*k;
}