#100pts code 但错最后一组

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
	int v, h, ans;//h 取余， ans 实际 
	friend bool operator < (node n, node n1)
	{
		return n.ans > n1.ans;
	}
};
int n, m, k, h[10010][10010];
int ans1[10010][105];
bool vis[10010][105];
priority_queue<node> que;
vector<int> vec[10010];
	
void bfs()
{
	node Temp;
	Temp.v = 1;
	Temp.h = 0;
	Temp.ans = 0; 
	que.push(Temp);
	ans1[1][0] = 0;
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			ans1[i][j] = 0x7f7f7f7f;
		}
	}
	
	while (!que.empty())
	{
		node temp = que.top();
//		cout << "当前点：" << temp.v << endl; 
		que.pop();
		if (vis[temp.v][temp.h] == 1) continue;
		vis[temp.v][temp.h] = 1;
		for (int i = 0; i < vec[temp.v].size(); i++)
		{
			node n1;
			n1.v = vec[temp.v][i];
			n1.h = (temp.h + 1) % k;
			n1.ans = temp.ans + 1;
			if (n1.ans < h[temp.v][n1.v])
			{
				n1.ans = n1.ans + (ceil((h[temp.v][n1.v] - temp.ans) * 1.0 / k) * k);
			}
			if (n1.ans < ans1[n1.v][n1.h])
			{
				ans1[n1.v][n1.h] = n1.ans;
				que.push(n1);
			}
		 } 
	}	
}
	
int main()
{
	memset(ans1, -1, sizeof(ans1));
	memset(h, -1, sizeof(h));
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)
	{
		ll u, v, num;
		cin >> u >> v >> num;
		if (h[u][v] == -1)
		{
			h[u][v] = num;
			vec[u].push_back(v);
		}
 	
	}
	 
	
	bfs();
		
	if (ans1[n][0] == 0x7f7f7f7f)
	{
		cout << -1; 
	} 
	else
	{
	 	cout << ans1[n][0]; 
	}
//	cout << ans1[n][0];
	return 0;
}

RECORD