#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
typedef long long ll;
int n,m,k,cnt,hd[maxn];
ll dis[maxn][105];
int vis[maxn][105];
struct edge{
	int u,to,nxt;
	ll w;
}e[maxn<<1];
void add(int u,int v,ll w){
	e[++cnt].nxt=hd[u];
	e[cnt].to=v;e[cnt].u=u;
	e[cnt].w=w;hd[u]=cnt;
}
typedef pair<ll,int> pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
void dij(){
	dis[1][0]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;
		ll t=q.top().first;
		q.pop();
		if(vis[u][t%k]) continue;
		vis[u][t%k]=1;
		ll tim;
		for(int i=hd[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(t>=e[i].w) tim=t;
			else tim=((e[i].w-t+k-1)/k)*k+t; 
			if(dis[v][(tim+1)%k]>=tim+1){
				dis[v][(tim+1)%k]=tim+1;
				q.push(make_pair(tim+1,v));
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
	}
	memset(dis,0x3f,sizeof dis);
	dij();
	if(dis[n][0]==0){
		puts("-1");
		return 0;
	}
	printf("%lld\n",dis[n][0]);
	return 0;
}