#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=2e6+5;
long long n,m,kk;
long long to[M],val[M],nxt[M],h[N],cnt;
long long dis[N][105];
bool vis[N][105];
void add(long long u,long long v,long long w){
	to[++cnt]=v;
	val[cnt]=w;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
struct node{
	long long u,w;
	friend bool operator<(node a,node b){
		return a.w<b.w;
	}
};
priority_queue<node> q;
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[1][0]=0;
	q.push(node{1,0});
	while(!q.empty()){
		node k=q.top(); q.pop();
		if(vis[k.u][k.w%kk]) continue;
		vis[k.u][k.w%kk]=1;
		for(int i=h[k.u];i;i=nxt[i]){
			long long t=0;
			if(k.w>=val[i]) t=k.w;
			else t=((val[i]-k.w+kk-1)/kk)*kk+k.w;
			if(dis[to[i]][(t+1)%kk]>t+1){
				dis[to[i]][(t+1)%kk]=t+1;
				q.push(node{to[i],t+1});
			}
		}
	}
}
int main(){
	cin>>n>>m>>kk;
	for(int i=1;i<=m;i++){
		long long u,v,t; cin>>u>>v>>t;
		add(u,v,t);
	}
	Dijkstra();
	if(!vis[n][0]) cout<<-1;
	else cout<<dis[n][0];
	return 0;
}