#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e4;
int head[MAXN];
struct Node{
	int to, next, w;
}e[MAXN];
int cnt;
void init()
{
	for(int i = 0; i < MAXN; i++)
	{
		head[i] = -1;
	}
}

void add(int x, int y, int w)
{
	e[cnt].to = y;
	e[cnt].next = head[x];
	e[cnt].w = w;
	head[x] = cnt++;
}

int n, m, k;
struct node{
	int v, num;
	//v当前的时间 
	friend bool operator <(node a, node b){
		return a.v < b.v;
	}
};
priority_queue<node> q;
bool vis[MAXN][100 + 5];//
void dij()
{
	q.push({0, 1});
	while(!q.empty())
	{
		node now = q.top();
		q.pop();
		vis[now.num][now.v % k] = true;
		if(vis[n][0] == true)
		{
			cout << now.v;
			return;
		}
		for(int i = head[now.num]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			int sum = now.v;//hua fei
			//1 0
			if(e[i].w > now.v)
			{
				int ssum = (e[i].w - now.v) / k;// ge shu
				if((e[i].w - now.v) % k != 0)ssum++;
				sum += k * ssum;
			}
			sum++;
			if(vis[v][sum % k] == true)
			{
				continue;
			}
			
			q.push({sum, v});
		}
	}
	
	cout << -1;
}
 main()
{
	//k
	//k, 2k, 3k, 4k
	//通过边权-k
	init();
	cin >> n >> m >> k;
	while(m--){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
	}
	dij();
	return 0;
}