代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MX = 20005;
int n, m, k, u[MX], v[MX], a[MX], dis[MX][105];
bool vis[MX][105];

struct Edge {
	int to, lw;
};

struct Node {
	int id, x;
	bool operator<(const Node &B) const {
		return B.x < x;
	}
};
vector<Edge> g[MX];
priority_queue<Node> q;

void dij() {
	q.push((Node) {
		1, 0
	});
	memset(dis, 127, sizeof(dis));
	dis[1][0] = 0;

	while (q.size()) {
		int x = q.top().id, p = q.top().x, t;

		if (vis[x][p % k])
			continue;

		vis[x][p % k] = 1;
		q.pop();

		for (int i = 0; i < g[x].size(); i++) {
			Edge y = g[x][i];

			if (p >= y.lw)
				t = p;
			else
				t = ceil(1.0 * (y.lw - p) / k) * k + p;
			if (dis[y.to][(t + 1) % k] > t + 1) {
				dis[y.to][(t + 1) % k] = t + 1;
				q.push((Node) {
					y.to, t + 1
				});
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);

	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", u + i, v + i, a + i);
		g[u[i]].push_back((Edge) {
			v[i], a[i]
		});
	}

	dij();
	printf("%d\n", (vis[n][0] ? dis[n][0] : -1));
	return 0;
}

求调