#include<bits/stdc++.h>
using namespace std;
const int M = 2e6 + 10; typedef pair<int, int> pii;
int n, m, cnt, k, nxt[M], to[M], h[M], vis[M], dis[M], tl[M];
priority_queue<pii, vector<pii>, greater<pii> > djk;//dis, node
int read() {
	int f = 1, a = 0;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		a = (a << 1) + (a << 3) + (c ^ 48);
		c = getchar();
	}
	return a * f;
}
void add(int u, int v, int w) {
	to[++cnt] = v;
	tl[cnt] = w;
	nxt[cnt] = h[u];
	h[u] = cnt;
}
void dijk() {
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	djk.push(make_pair(0, 1));
	while(!djk.empty()) {
		int u = djk.top().second; djk.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = h[u]; i; i = nxt[i]) {
			int t = 0;
			if(dis[u] >= tl[i]) t = dis[u];
			else t = (tl[i] - dis[u] + k - 1) / k * k;
			if(dis[to[i]] > t + 1) {
				dis[to[i]] = t + 1;
				djk.push(make_pair(dis[to[i]], to[i]));
			}
		} 
	}
}
int main() {
	n = read(), m = read(), k = read();
	for(int i = 1, u, v, w; i <= m; ++i) {
		u = read(), v = read(), w = read();
		for(int j = 0; j < k; ++j) { 
			if(j == k - 1)//如果是最后一层
				add(u + n * j, v, w);
			else add(u + n * j, v + n * (j + 1), w);//一般情况
		}
	}
//	for(int i = 1; i <= k * n; ++i) {
//		cout << i << ": ";
//		for(int j = h[i]; j; j = nxt[j])
//			cout << to[j] << ' '; 
//		cout << endl;
//	}
	dijk();
//	for(int i = 1; i <= k * n; ++i) cout << dis[i] << ' ';
	if(dis[n] == 0x3f3f3f3f) cout << -1;
	else cout << dis[n];
	return 0;
}