[CSES] Flight Discount

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<vpll> v(n);
    rep(i, m) {
        ll a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        v[a].pb({ b, w });
    }


    vvll d(n, vll(2, inf)), vis(n, vll(2, 0));
    function <void(ll)> dij = [&](ll node) {
        d[node][0] = d[node][1] = 0;
        set<array<ll, 3>> st;
        rep(i, n) {
            rep(j, 2) {
                st.insert({ d[i][j], i, j });
            }
        }

        while (!st.empty()) {
            auto from = *st.begin();
            vis[from[1]][from[2]] = 1;
            st.erase(st.begin());

            for (auto child : v[from[1]]) {
                ll to = child.f;
                ll len = child.s;

                if (from[2] == 0) {
                    // 0 1
                    if (!vis[to][0]) {
                        if (from[0] + len < d[to][0]) {
                            st.erase(st.find({ d[to][0], to, 0 }));
                            d[to][0] = from[0] + len;
                            st.insert({ d[to][0], to, 0 });
                        }
                    }

                    if (!vis[to][1]) {
                        if (from[0] + len / 2 < d[to][1]) {
                            st.erase(st.find({ d[to][1], to, 1LL }));
                            d[to][1] = from[0] + len / 2;
                            st.insert({ d[to][1], to, 1LL });
                        }
                    }
                }
                else {
                    // 0
                    if (!vis[to][1]) {
                        if (from[0] + len < d[to][1]) {
                            st.erase(st.find({ d[to][1], to, 1 }));
                            d[to][1] = from[0] + len;
                            st.insert({ d[to][1], to, 1 });
                        }
                    }
                }
            }
        }
        };
    dij(0);
    ll ans = min(d[n - 1][0], d[n - 1][1]);
    cout << ans << "\n";

}