#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,ans = 1e10;
ll u,v,a;
struct N{
	ll id,t;
};
N c[20005][805];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>a;
		c[u][++c[u][0].id] = N{v,a};
	}
	queue<N> q;
	q.push(N{1,0});
	while(!q.empty()){
		N f = q.front();
		q.pop();
		if(f.t >= ans)continue;
		if(f.id == n){
			if(f.t % k == 0)ans = min(ans,f.t);
			continue;
		}
		for(int i=1;i<=c[f.id][0].id;i++){
			if(c[f.id][i].id == f.id)continue;
			if(f.t >= c[f.id][i].t)q.push(N{c[f.id][i].id,f.t+1});
			else q.push(N{c[f.id][i].id,f.t + ceil((c[f.id][i].t-f.t)*1.0/k)*k + 1});
		}
	}
	cout<<(ans == 1e10?-1:ans);
	return 0;
}

暴力BFS能90，考场大样例跑不出来