#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge {
	int to;
	int nxt;
	int a;
} e[2000006];
struct str {
	int id;
	int h;
	int ans;
	bool vis;
	bool operator < (const str &x) const {
        return ans > x.ans;
    }
} a[2000006];
int n,m,k,cnt;
priority_queue <str> q;
void add (int u,int v,int A) {
	cnt++;
	e[cnt].to = v;
	e[cnt].nxt = a[u].h;
	e[cnt].a = A;
	a[u].h = cnt;
}
signed main () {
	cin >> n >> m >> k;
	for (int i = 1;i <= n * k;i++) {
		a[i].id = i;
		a[i].h = 0;
		a[i].vis = 0;
	} 
	int u,v,A;
	for (int i = 1;i <= m;i++) {
		cin >> u >> v >> A;
		for (int j = 1;j <= k;j++) {
			add(u + (j - 1) % k * n,v + j % k * n,A);
		}
	}
	a[1].ans = 0;
	a[1].id = 1;
	q.push(a[1]);
	a[n].ans = -1;
	while (!q.empty()) {
		int p = q.top().id;
		if (p == n) {
			break;
		}
		q.pop();
		if (a[p].vis) {
			continue;
		}
		a[p].vis = 1;
		for (int i = a[p].h;i;i = e[i].nxt) {
			if (a[e[i].to].vis) {
				continue;
			}
			if (a[p].ans <= e[i].a) {
				int c = (e[i].a - a[p].ans + k - 1) / k * k;
				a[e[i].to].ans = a[p].ans + 1 + c;
			} else {
				a[e[i].to].ans = a[p].ans + 1;
			}
			q.push(a[e[i].to]);
		}
	}
	cout << a[n].ans << endl;
	return 0;
}