题解！！！

#include <bits/stdc++.h>
using namespace std;
int n,m,k,u,v,w;
vector<pair<int, int>> g[100005];
int dis[100005][105];  //dis[i][j]表示到 i 点，满足时间 mod k == j的最短时间
bool vis[100005][105];  //vis[i][j]表示到 i 点，满足时间 mod k == j 是否更新过
struct node{
	int u,t,dis;
	bool operator<(const node &a) const{
		return dis > a.dis;
	}
}; 
priority_queue<node> q;      //优先队列

void bfs(){
	memset(dis, 0x3f, sizeof(dis));
	q.push({1, 0, dis[1][0] = 0});
	while(!q.empty()){
		node head = q.top();
		q.pop();
		if(vis[head.u][head.t]) continue;
		vis[head.u][head.t] = 1;
		for(int i = 0; i < g[head.u].size(); i++){
			v = g[head.u][i].first, w = g[head.u][i].second;
			int tu = dis[head.u][head.t], tv = (head.t + 1) % k;
			if(tu < w){
				tu += (w - tu + k - 1) / k * k;
			}
			if(dis[v][tv] > tu + 1){
				dis[v][tv] = tu + 1;
				q.push({v, tv, dis[v][tv]});
			}
		}
	}
}

void init(){
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
    	cin >> u >> v >> w;
    	g[u].push_back(make_pair(v,w));
	}
	bfs();
	cout << (dis[n][0] == 0x3f3f3f3f ? -1 : dis[n][0]);
}

int main(){
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    
    init();

    fclose(stdin);
    fclose(stdout);
    return 0;
}