#include <bits/stdc++.h>
using namespace std;
#define int long long
//P9751 [CSP-J 2023] 旅游巴士(bus)
const int N=1e4+7,M=2e4+6,K=1e2+3,inf=0x3f3f3f3f3f3f3f3fll;
struct Edge{
	int v,w,nxt;//从u到v，开放时间w
}e[M];
struct node{
	int idx,w,r;
	bool operator<(const node&u)const{return w<u.w;}
	node(int xx,int ww,int rr){idx=xx;w=ww;r=rr;}
};
int n,m,k,cnt,head[M],d[N][K],vis[N][K];
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dijkstra(int st){
	memset(d,0x3f,sizeof(d));
	priority_queue<node> pq;
	pq.push(node(st,0,0));
	d[st][0]=0;
	while(!pq.empty()){
		node no=pq.top();pq.pop();
		if(vis[no.idx][no.r])continue;
		vis[no.idx][no.r]=1;
		int u=no.idx,w=no.w,r=no.r;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,ew=e[i].w;
			if(ew>w){
				d[v][(r+1)%k]=min(d[v][(r+1)%k],d[u][r]+((ew-w+k-1)/k)*k+1);
				pq.push(node(v,((ew-w+k-1)/k)*k+1+w,(r+1)%k));
			}else{
				d[v][(r+1)%k]=min(d[u][r]+1,d[v][(r+1)%k]);
				pq.push(node(v,w+1,(r+1)%k));
			}
		}
	}
}
signed main(){
//	freopen("bus.in","r",stdin);
//	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(1);
	if(d[n][0]!=inf)cout<<d[n][0];
	else cout<<-1;
	return 0;
}

调了2h没出来qwq