//P9751
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10005;
const int M = 20005;
const int K = 105;
const long long inf = 0x7f7f7f7f;
int head[N], node[M], ne[M], tot;
long long val[M], ans, dis[N][K];
int qi[N * K], qf[N * K], qh, qt;
int n, m, k, l, r, mid;
bool vis[N][K];
void add(int x, int y, long long w){
	tot++;
	node[tot] = y;
	val[tot] = w;
	ne[tot] = head[x];
	head[x] = tot;
	return;
}
bool check(long long T){
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < k; j++){
			dis[i][j] = inf;
			vis[i][j] = false;
		}
	}
	dis[n][0] = T;
	vis[n][0] = true;
	qh = 1;
	qt = 1;
	qi[qt] = n;
	qf[qt] = 0;
	while (qh <= qt){
		int u = qi[qh];
		int f = qf[qh];
		qh++;
		for (int i = head[u]; i != -1; i = ne[i]){
			int v = node[i];
			if (vis[v][(f + 1) % k]){
				continue;
			}
			if (dis[u][f] <= val[i]){
				continue;
			}
			vis[v][(f + 1) % k] = true;
			dis[v][(f + 1) % k] = dis[u][f] - 1;
			qt++;
			qi[qt] = v;
			qf[qt] = (f + 1) % k;
		}
	}
	return (vis[1][0]);
}
int main(){
//	freopen("input.in", "r", stdin);
	memset(head, -1, sizeof(head));
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++){
		int u, v;
		long long w;
		scanf("%d%d%lld", &u, &v, &w);
		add(v, u, w);
	}
	ans = -1;
	l = 1;
	r = (1000000 + k - 1) / k;
	while (l <= r){
		mid = (l + r) >> 1;
//		printf("%d %d %d\n", l, r, mid);
		if (check(mid * k)){
			ans = mid * k;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	printf("%lld", ans);
	return 0;
}

记录