#include <bits/stdc++.h>
#define ll long long
#define ii ((i + 1) % k)

using namespace std;

const int N = 1e4 + 10;
const int M = 2e4 + 10;
const int K = 100 + 10;
const int INF = 1e9;

inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	for ( ; !isdigit(c); c = getchar())  if (c == '-') w = -1;
	for ( ; isdigit(c); c = getchar())   s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

struct EDGE{
	int to;
	int pub;//开放时间
};
struct Node{
	int Id;
	int val;
	bool operator <(const Node a)const{
		return a.val < val;
	}
};
int n, m, k, u, v, a; vector<EDGE> G[N];
int dis[N][K]; bool vis[N][K];//表示 % k 的最早的到达时间 

inline int Wait(int lim, int from)
{
	int tmp = (lim - from - 1) / k;
	if((lim - from - 1) % k > 0) tmp ++;
	return tmp * k;
}

priority_queue<Node> pq;
inline void Dijkstra()//可以求出到一个点的最晚时间，使得dis[i] >= a[i],且dis[n]最小; 如果dis[i] < a[i] 此路不通
{  
	
	for(int i = 1; i <= n; i ++){
		for(int j = 0; j < k; j++){
			dis[i][j] = INF;
		}
	}//处理时间限制的方法是对的。问题是找到一条长度为k * d 且最短的路径
	dis[1][0] = 0;
	pq.push({1,dis[1][0]});
	while(!pq.empty())
	{
		int tp = pq.top().Id;
		int i = pq.top().val;
		pq.pop();
		if(vis[tp][i % k] == 1) continue;//if(vis[tp] == 1) conintue;这一句因为vis没有变成二维，导致无法走环
		vis[tp][i % k] = 1;
		for(auto [to, pub] : G[tp]){
			int t = (i + 1) % k;
			if(i >= pub){
				if(dis[to][t] > i + 1){
					dis[to][t] = i + 1;
					pq.push({to,dis[to][t]});
				}
			}
			else{
				int tmp = Wait(pub, i);
				if(dis[to][t] > i + 1 + tmp){
					dis[to][t] = i + 1 + tmp;
					pq.push({to,dis[to][t]});
				}
			}
		}
	}
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);//dis[1] = 0 + d * k;
	cin>> n >> m >> k;//如果倒着推来，离开时必然是k的整数 dis[i] 表示到达它的最早时间 可以 dis[i] + d * k;
	for(int i = 1; i <= m; i++){// 连接n的点，k 必须整除 dis[i] 
		cin>> u >> v >> a;
		G[u].push_back({v,a});
	}
	Dijkstra();
//	for(int i = 1; i <= n; i ++) cout<< dis[i] <<"\n";
	if(dis[n][0] < INF) cout<< dis[n][0] <<"\n";
	else cout<<"-1\n";
	return 0;
}