#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000;
int n,m,k;
struct edge{
	int to,w,next;
}e[MAXN];
int cnt,head[MAXN];
void add_edge(int u,int v,int w){
	cnt++;
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int dis[MAXN];
bool vis[MAXN];//每个点只需要以这个点为中心松弛一次，而不是到这个点的边被松弛一次
struct node{
	int v,w;
	friend bool operator <(node a,node b){
		return a.w>b.w;
	}
};
priority_queue<node>q;
void dijkstra_heap(int s){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push((node){s,0});
	while(q.empty()==false){
		int u=q.top().v;
		q.pop();
		if(vis[u]==false){
			vis[u]=true;
			for(int i=head[u];i!=0;i=e[i].next){
				int tmp=dis[u]+1;
				if(tmp<e[i].w)
					tmp+=ceil(1.0*(e[i].w-(dis[u]+1))/k)*k;
				if(tmp<dis[e[i].to]){
					dis[e[i].to]=tmp;
					q.push((node){e[i].to,tmp});
				}
			}
				
		}
	}
}

int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
		for(int j=1;j<k;j++)
			add_edge(u+(j-1)*n,v+j*n,w);
	}
	dijkstra_heap(1);
	if (dis[n] == 0x3f3f3f3f)
		cout<<-1<<endl;
	else
		cout<<dis[n]<<endl;
	return 0;
}