#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
int read(){int x = 0, f = 1;char ch = getchar(); while(ch < '0' or ch > '9'){if(ch == '-'){f = -1;} ch = getchar();} while(ch >= '0' and ch <= '9'){x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}return x * f;}
void write(int x){if(x < 0)	putchar('-'), x = -x;if(x >= 10)	write(x / 10);putchar(x % 10 + '0');}
#define put() putchar(' ')
#define endl puts("")
#define pb emplace_back
const int MAX = 1e4 + 10;

struct node{
	int v, w;
}; vector <node> g[MAX];

int f[MAX][105];

struct edge{
	int from, val, modd;
	bool operator < (const edge &x) const{
		return val > x.val;
	}
};

void dji(int u, int k, int n){
	priority_queue <edge> que;
	que.push(edge{1, 0, 0});
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= 104; j++){
			f[i][j] = mininf;
		}
	}
	f[1][0] = 0;
	while(!que.empty()){
		int u = que.top().from, val = que.top().val, modd = que.top().modd;
		que.pop();
		if(f[u][modd] != val)	continue;
		for(auto V : g[u]){
			int v = V.v, w = V.w;
			int cost = val + 1;
			if(w > val){
				cost = val + (w - val + k - 1) / k * k + 1;
			}
			if(f[v][(modd + 1) % k] > cost){
				f[v][(modd + 1) % k] = cost;
				que.push(edge{v, cost, (modd + 1) % k});
			}
		}
	}
	if(f[n][0] >= mininf)	puts("-1");
	else write(f[n][0]), endl;
}

void solve(){
	int n = read(), m = read(), k = read();
	for(int i = 1; i <= m; i++){
		int u = read(), v = read(), w = read();
		g[u].pb(node{v, w});
	}
	dji(1, k, n);
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}