TLE on #12,13,16,17

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

const int N = 1e4 + 5, M = 2e4 + 5, K = 105;

int n, m, k;

vector<pii> g[N * K];

inline int id(int x, int i) {return x + n * i;}

bool check(int x) {
    bitset<N * K> vis;
    queue<pii> q;
    q.emplace(id(n, 0), x * k);
    vis[id(n, 0)] = 1;
    while (!q.empty()) {
        auto [u, t] = q.front(); q.pop();
        for (auto [v, w]: g[u]) {
            if (t > w && !vis[v]) {
                if (v == 1) return true;
                q.emplace(v, t - 1);
                vis[v] = 1;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        for (int j = 0; j < k; j++) {
            g[id(v, (j + 1) % k)].emplace_back(id(u, j), w);
        }
    }
    int l = 0, r = 2e7, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << max(ans, ans * k) << "\n";
    return 0;
}