#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e4 + 5;
vector<pair<int, int>> es[MAXN];

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < m; ++i) {
		int u, v, a;
		cin >> u >> v >> a;
		es[v].emplace_back(u, a);
	}

	auto ok = [&](int x) {
		queue<pair<int, int>> q;
		q.emplace(x * k, n);
		while(!q.empty()) {
			auto [t, u] = q.front();
			q.pop();
			if(u == 1 && t % k == 0) {
				return 1;
			}
			for(auto &[v, a] : es[u]) {
				if(t - 1 < a)
					continue;
				if(v == 1 && t % k == 1)
					return 1;
				if(t > (x - 1) * k) {
					q.emplace(t - 1, v);
				}
			}
			// cerr << t << ' ' << u << '\n';
		}
		return 0;
	};

	int l = 0, r = 1e9;
	if(!ok(r)) {
		cout << "-1\n";
		return ;
	}
	while(l < r - 1) {
		int mid = l + r >> 1;
		if(ok(mid))
			r = mid;
		else
			l = mid;
	}
	cout << r * k << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("D:\\Desktop\\bus2.in", "r", stdin);

	solve();
	return 0;
}