#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 10010;
const int M = 20010;
const int K = 110;          
int n, m, k;
int head[N], e[M], w[M], ne[M], idx;
queue<PII> q;
int depth[N][K];
void add(int u, int v, int a){
	e[idx] = v;
	w[idx] = a;
	ne[idx] = head[u];
	head[u] = idx ++; 
}
int bfs(int start){
	memset(depth, -1, sizeof depth);
	q.push(make_pair(1, 0));
	depth[1][0] = start;
	while(q.size()){
		PII p = q.front(); q.pop();
		int u = p.first, x = p.second;
		for(int i = head[u] ; i != -1 ; i = ne[i]){
			int v = e[i], a = w[i];
			if(depth[v][(x + 1) % k] == -1 && depth[u][x] >= a) {
				q.push(make_pair(v, (x + 1) % k));
				depth[v][(x + 1) % k] = depth[u][x] + 1;  
			}       
		}
	}
	if(depth[n][0] != -1) return depth[n][0];
	return -1;
}
int main(){
	memset(head, -1, sizeof head);
	scanf("%d%d%d", &n, &m, &k);
	int mintime = 0, maxtime = 0;
	while(m --){
		int u, v, a;
		scanf("%d%d%d", &u, &v, &a);
		add(u, v, a);
		maxtime = max(maxtime, a);
	}
	int ans = 0x3f3f3f3f;
	int l = 0, r = 2 * maxtime / k + 1;
	while(l < r){
		int mid = (l + r) >> 1, res;
		if((res = bfs(mid * k)) != -1){
			r = mid;
			ans = min(ans, res); 
		}
		else l = mid + 1; 
	}
	if(ans != 0x3f3f3f3f) printf("%d", ans);
	else printf("-1\n");
	return 0;
}