#include <bits/stdc++.h>
#define rg register
#define il inline
#define int long long
using namespace std;
int n,m,k,t,dis[10005][105];
bool vis[10005];
struct node{
	int v,a;
};
struct aa{
	int dian,t;
};
vector<node> d[10005];
queue<aa> q;
void bfs(int x){
	memset(dis, 127, sizeof(dis));
	dis[x][0]=0;
	q.push({x,0});
	while(!q.empty()){
		aa dian=q.front();//当前端点 
		q.pop();
		x = dian.dian;//起点
		t = dian.t;//x点的时间
		int s = (t+1)%k;//下一个点的时间 
		if(dis[x][t%k] > dis[n][0]) continue;
		for(rg int i = 0; i < d[x].size(); i++ ){
			int V=d[x][i].v, A=d[x][i].a, u = 0;//增加的时间 
			
			if(A > t){
				u = (A-t+k-1)/k*k;
			}
			if(dis[V][s] > dis[x][t%k] + u + 1){
				dis[V][s] = dis[x][t%k] + u + 1;
				q.push({V, dis[V][s]});
			}
		}
	}
	
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(rg int i = 0; i < m; i++ ){
		int x,y,z;
		cin>>x>>y>>z;
		d[x].push_back({y,z});
	}
	bfs(1);
	if(dis[n][0] < 2139062143) cout<<dis[n][0];
	else cout<<"-1";
	return 0;
}