#include <bits/stdc++.h>
#define int long long
#define N 1000010
using namespace std ;
const int inf = (int)2e18 ;
typedef pair<int , int> pii ;
int n , m , k , dis[N] , vis[N] ;
struct node {
	int u , t ;
};
vector<node>g[N] ;
priority_queue<pii , vector<pii> , greater<pii> >q ;
signed main() {
	scanf("%lld%lld%lld" , &n , &m , &k) ;
	for(int i = 1 ; i <= m ; i++) {
		int u , v , a ;
		scanf("%lld%lld%lld" , &u , &v , &a) ;
		for(int j = 0 ; j < k ; j++) {
			g[j * n + u].push_back((node){(j + 1) % k * n + v , a}) ;
		}
	}
	for(int i = 1 ; i <= n * k ; i++) {
		dis[i] = inf ;
	}
	q.push(make_pair(0 , 1)) ;
	dis[1] = 0 ;
	while(q.size()) {
		pii p = q.top() ; q.pop() ;
		if(vis[p.second]) continue ;
		vis[p.second] = 1 ;
		for(int i = 0 ; i < (int)g[p.second].size() ; i++) {
			node now = g[p.second][i] ;
			int tmp = dis[p.second] + 1 ;
			if(now.t > tmp) {
				tmp += (int)ceil(1.0 * (now.t - tmp) / k) * k ;
			}
			if(tmp < dis[now.u]) {
				dis[now.u] = tmp ;
				if(vis[now.u]) continue ;
				q.push(make_pair(tmp , now.u)) ;
			}
		}
	}
	if(dis[n] == inf) puts("-1") ;
	else printf("%lld" , dis[n]) ;
	return 0 ;
}

思路很简单，就是分层图+dijkstra , 应该能看懂吧