#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 0x3f3f3f3f;
const ll N = 1e6+10;
vector<pair<ll, ll> > G[N];
ll d[N][105];
ll vis[N][105];
struct node {
	ll u, i, d;
	bool operator<(const node &rhs) const {
		return d > rhs.d;
	}
};
ll n, m, k;

int main() {
	cin>>n>>m>>k;
	while (m--) {
		ll u, v, w;
		cin>>u>>v>>w;
		G[u].push_back({v, w});
	}
	
	memset(d, 0x3f, sizeof d);
	
	priority_queue<node> q;
	q.push({1, 0, d[1][0] = 0});
	while (q.size()) {
		ll u = q.top().u, i = q.top().i;
		q.pop();
		if (vis[u][i]) continue;
		vis[u][i] = 1;
		for (auto [v, w] : G[u]) {
			int t = d[u][i], j = (i + 1) % k;
			if (t < w) {
				t += (w - t + k - 1) / k * k;
			}
			if (d[v][j] > t + 1) {
				q.push({v, j, d[v][j] = t + 1});
			}
		}
	}
	if (d[n][0] == INF) {
		d[n][0] = -1;
	}
	cout<<d[n][0]<<"\n";
	return 0;
}