WA on #2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, k, dis[N][105], vis[N][105];
struct edge{
	int to, wei;
};
vector<edge> G[N];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void Dij(int S){
	memset(dis, 0x3f, sizeof dis);
	dis[S][0] = 0;
	q.push({0, S});
	while(!q.empty()){
		int u = q.top().second, p = q.top().first;
		q.pop();
		if(vis[u][p % k]) continue;
		vis[u][p % k] = 1;
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u][i].to, w = G[u][i].wei, t;
			if(p >= w) t = p;
			else t = p + ((w - p + k - 1) / k) * k;
			if(dis[v][(t + 1) % k] > t + 1){
				dis[v][(t + 1) % k] = t + 1;
				q.push({t + 1, v}); 
			}
		}
	}
}

signed main(){
	scanf("%lld%lld%lld", &n, &m, &k);
	for(int i = 1, x, y, z; i <= m; i++){
		scanf("%lld%lld%lld", &x, &y, &z);
		G[x].push_back(edge{y, z});
	}
	Dij(1);
	if(!dis[n][0]) puts("-1");
	else printf("%lld\n", dis[n][0]);
	return 0;
}