旅游巴士這道題在一年之前的csp-j中并沒有做（我是一個蒟蒻）
回看本題，又有了新的想法
對于每一層i我們將其看成走到這是的時間j mod k的余數(shù)
很顯然，為了讓我們更快的通過，等待時間+當前時間>=限制時間是最優(yōu)的

/*
使用分層圖，跑dijkstra堆優(yōu)化的最短路
在限制時間那部分，若小于限制時間，可每次等k的倍數(shù)的時間，使得：等待時間+當前時間>=限制時間
因為離開時間是k的倍數(shù)，所以我們盡量使每次到達一個點的時間也是k的倍數(shù)，這樣離開時就不用再等太久了
按照上述思路敲代碼是最優(yōu)的 
vector數(shù)組graph是用來存儲分層圖的，為graph_node類型的 
min_time[i]表示走到分層圖的第i個節(jié)點的最優(yōu)時間 
q 是優(yōu)先隊列（堆）priority_queue，是graph_node結構體為類型的，進行重載小于號，方便堆排序 
時間復雜度 O(nk log(nk)) 
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct graph_node{
	int to_node;
	int cur_time;
	bool operator<(const graph_node &s1)const{
		return cur_time>s1.cur_time;
	}
};
vector<graph_node>graph[N];
int n,m,k;
int min_time[N];
void dijkstra(int start){
	for (int i=1;i<=n*k;i++)min_time[i]=0x3f3f3f3f;
	priority_queue<graph_node>q;
	q.push({start,0});min_time[1]=0;
	while (!q.empty()){
		int cur=q.top().to_node,t=q.top().cur_time;q.pop();
		if (t<=min_time[cur]){
			for (const auto&road:graph[cur]){
				int plat=min_time[cur]+1,limt=road.cur_time;
				if (min_time[cur]<limt)plat+=ceil((limt-min_time[cur])*1.0/k)*k;
				if (plat<min_time[road.to_node]){
					min_time[road.to_node]=plat;
					q.push({road.to_node,plat});
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	int x,y,len;
	for (int i=1;i<=m;i++){
		cin>>x>>y>>len;
		for (int j=0;j<k;j++)
			graph[j*n+x].push_back({(j+1)%k*n+y,len});
	}
	dijkstra(1);
	if (min_time[n]==0x3f3f3f3f)cout<<-1;
	else cout<<min_time[n];
	return 0;
}