#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10005;
int n,m,s,t,K,p,f[N][100];//f[i][j]当前在i号点，%k=j的最早时间 
int vis[N][100];
struct node{
	int f,u,x;
	bool operator<(const node &k)const{
		return f>k.f;
	}
};
priority_queue<node> q;
vector<pair<int,int>> e[N]; 
void dijkstra(){
	memset(f,0x3f,sizeof(f));
	f[1][0]=0;int tmp;
	q.push({f[1][0],1,0});
	while (!q.empty()){
		int u=q.top().u;
		int x=q.top().x;
		q.pop();
		if (vis[u][x]) continue;
		vis[u][x]=1;
		for (auto [v,p]:e[u]){
			if (p<=f[u][x]) {
				if (f[v][(x+1)%K]>f[u][x]+1){
					f[v][(x+1)%K]=f[u][x]+1;
					q.push({f[v][(x+1)%K],v,(x+1)%K});	
				}
			}
			else {
				tmp=(p-f[u][x]-1)/K+1;
				tmp=f[u][x]+tmp*K;
				if (f[v][(x+1)%K]>tmp+1){
					f[v][(x+1)%K]=tmp+1;
					q.push({f[v][(x+1)%K],v,(x+1)%K});	
				}
			}
		}
	}
}
int main()
{
//	freopen("in.txt","r",stdin); 
	cin>>n>>m>>K;
	for (int i=1;i<=m;++i){
		cin>>s>>t>>p;
		e[s].push_back({t,p});
	} 
	dijkstra();
	cout<<(f[n][0]<0x3f3f3f3f?f[n][0]:-1);
}