#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vint vector<int>
#define pii pair<int,int>
#define que queue<int>
int n,m,k,ans(2e9);
vector<pii> e[20005];
int dij(int s){
	priority_queue<pii,vector<pii>,greater<pii>> q;
	q.push({s,1});
	while(!q.empty()){
		pii u=q.top();
		q.pop();
		if(u.first>=ans) return 2e9;
		if(u.second==n&&u.first%k==0)
			return u.first;
		for(auto v:e[u.second])
			if(u.first+1>=v.second)
				q.push({u.first+1,v.first});
	}
	return 2e9;
}
signed main(){
    int T=clock();
	cin>>n>>m>>k;
	int flag=1;
	for(int i=1,u,v,a;i<=m;i++){
		cin>>u>>v>>a;
		e[u].push_back({v,a});
	}
	for(int i=0;clock()-T<=950000;i+=k)
		ans=min(dij(i),ans);
	cout<<(ans==2e9?-1:ans);
	return 0;
}

思路就是枚举k然后跑迪杰斯特拉，加了个卡时间，和 if(u.first>=ans) return 2e9; 这么个小剪枝，结果 https://www.luogu.com.cn/record/131115822 85分，难蚌。

顺便问问大佬为什么会挂 8~10 啊 QwQ