70分求调

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long 
const int N = 1e4 + 10;
#define pii pair <int, int>
#define mk make_pair
#define ps push
int n, m, k;
struct way {
    int to, w;
};
vector <way> G[N];
int dis[N];
bool vis[N];
void dij () {
    for (int i = 1; i <= n; i++) dis[i] = INT_MAX;
//    memset (dis, 0x3f, sizeof dis);
    dis[1] = k;
    // cout << dis[n] << "\n";
    priority_queue <pii, vector <pii>, greater <pii> > q;
    q.ps (mk (k, 1));
    while (!q.empty ()) {
        auto [z, u] =  q.top (); q.pop ();
        if (vis[u]) continue;
        vis[u] = true;
        // cout << u << "\n";
        for (auto [v, w] : G[u]) {
            if (dis[u] >= w) {
                // cout << u << ' ' << v << "\n";
                // cout << dis[v] << ' ' << dis[u] << "\n";
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    q.ps (mk (dis[v], v));
                }
            } else {
                if (dis[v] > w + 1) {
                    dis[v] = w + 1;
                    q.ps (mk (dis[v], v));
                }
            }
        }
    }
    if (dis[n] == INT_MAX) cout << "-1\n";
    else cout << ((dis[n] + (k - 1)) / k) * k << "\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back ({v, w});
    }
    dij ();
	return 0;
}