[CSES] Investigation

void solve() {
    ll n, m;
    cin >> n >> m;

    vector<vpll> v(n);
    rep(i, m) {
        ll x, y, w;
        cin >> x >> y >> w;
        --x, --y;
        v[x].pb({ y, w });
    }

    vll d(n, inf);
    function<void(ll)> dij = [&](ll node) {
        d[node] = 0;

        set<pll> st;
        st.insert({ d[node], node });

        while (sz(st)) {
            auto cur = *st.begin();
            st.erase(st.begin());
            if (cur.f != d[cur.s]) continue;

            for (auto& child : v[cur.s]) {
                if (d[child.f] > cur.f + child.s) {
                    d[child.f] = cur.f + child.s;
                    st.insert({ d[child.f], child.f });
                }
            }
        }
        };
    dij(0);
    debug(d);

    vvll g(n);
    rep(i, n) {
        for (auto& child : v[i]) {
            if (d[child.f] == d[i] + child.s) {
                g[i].pb(child.f);
            }
        }
    }
    debug(g);


    vll topo, vis(n);
    function <void(ll, ll)> dfs = [&](ll node, ll pr) {
        vis[node] = 1;
        for (auto& child : g[node]) {
            if (!vis[child]) {
                dfs(child, node);
            }
        }
        topo.pb(node);
        };
    dfs(0, 0);
    reverse(all(topo));
    debug(topo);

    vll dp(n, 0), dpmx(n, -inf), dpmn(n, inf);
    dp[0] = 1;dpmx[0] = dpmn[0] = 0;
    for (auto& node : topo) {
        for (auto& child : g[node]) {
            dp[child] += dp[node];
            dp[child] %= mod;

            dpmx[child] = max(dpmx[child], dpmx[node] + 1);
            dpmn[child] = min(dpmn[child], dpmn[node] + 1);
        }
    }
    debug(dp);
    debug(dpmx);
    debug(dpmn);

    cout << d[n - 1] << " " << dp[n - 1] << " " << dpmn[n - 1] << " " << dpmx[n - 1] << "\n";
}