TLE在预料之中，但不知道为什么WA。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, u, w, a, f[10005];
struct node{
	int w, a;
};
vector<node> v[10005];
void dfs(int x, int t){
	if(f[x] <= t){
		return;
	}
	if(v[x].size() == 0){
		if(t % k == 0 || x != n){
			f[x] = t;
		}
	}
	for(int i = 0; i < v[x].size(); i++){
		int to = v[x][i].w;
		int val = v[x][i].a;
		if(t < val){
			if(f[x] <= (t + ceil((1.0 * val - 1.0 * t) / k) * k)){
				continue;
			}
			if((long long)(t + ceil((1.0 * val - 1.0 * t) / k) * k) % k == 0 || x != n){
				f[x] = t + (val - t + k - 1) / k * k;
			}
			dfs(to, f[x] + 1);
		}
		else{
			if(t % k == 0 || x != n){
				f[x] = t;
			}
			dfs(to, t + 1); 
		} 
	}
}
signed main(){
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++){
		cin >> u >> w >> a;
		v[u].push_back({w, a});
	}
	memset(f, 0x3f, sizeof(f));
	dfs(1, 0);
	cout << f[n];
	return 0;
}