#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10;
ll n, m, k, dis[N][110];
bool p[N][110];
vector<ll> vec[N], g[N];
inline ll read() {
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x) {
	if(x < 0) {
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
priority_queue<pair<ll, ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > q;
inline void dij(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s][0] = 0;
    q.push({s, 0});
    while(!q.empty()){
    	ll u = q.top().first, ti = q.top().second;
		q.pop();
		if(p[u][ti % k]) continue;
		p[u][ti % k] = true;
		for(int i = 0; i < vec[u].size(); ++ i){
			ll v = vec[u][i], G = g[u][i], t;
			if(ti >= G) t = ti;
			else t = ((G - ti - 1 + k) / k) * k + ti;
			++ t;
			if(dis[v][t % k] > t){
				dis[v][t % k] = t;
				q.push({v, t});
			}
		} 
	}
}
signed main() {
	n = read(), m = read(), k = read();
	for(int i = 1; i <= m; ++ i) {
		ll u = read(), v = read(), w = read();
		vec[u].push_back(v);
		g[u].push_back(w);
	}
	dij(1);
	write(!p[n][0] ? -1 : dis[n][0]);
	return 0;
}

30pts，思路为dij