is it still valid or did someone win ?

I have hacked your solution. https://cses.fi/problemset/hack/1671/result/33262/

The explanation is that your code does kinda bfs, but you can add a vertex again, and that is the catch.

I would have been alot easier if you didn't randomly shuffle the adjacent list(also the MAGIC thing).We kind of use a little bit probability. We make the graph like this from every vertex i put edge to next k=5 (from i+2 , .. n), vertexes with weight 2*(n-i). At the end add egdes i to i+1 with weight 1. First it visits all vertex with wrong distance with some probability,then it visits them with correct once.

I tried some value for k but the worst I found was for k=5.

different hack: https://cses.fi/problemset/hack/1671/result/33264/

vector<std::array<int, 3>> gen(int N=66665) {
    vector<Edge> edges;
    for (int i = 0; i < N / 2; ++i) edges.push_back({i, N / 2, N - 2*i});
    for (int i = 0; i < N / 2; ++i) edges.push_back({i, N+i, 1});
    for (int i = 0; i < N / 2; ++i) edges.push_back({N+i, N+N/2, 3*N-2*i});
    for (int i = N / 2 + 1; i < N; ++i) edges.push_back({N / 2, i, 1});
    for (int i = 0; i < N / 2 - 1; ++i) edges.push_back({i, i + 1, 1});
    return edges;
}

The testcase is basically the first result on google: https://stackoverflow.com/a/76249282 which is already robust against shuffling edges. The only thing that needs to be changed is to handle MAGIC. This can be done by adding new edges to dummy vertices that just avoid swapping vertices to the front:

• For $$$i\in[0,N/2)$$$, add edge $$$i\to N+i$$$ with weight $$$0$$$
• For $$$i\in[N,N+N/2)$$$, add edge $$$i\to N+N/2$$$ with weight $$$4N-i$$$

This is a working testcase. However, you will realize that this problem does not allow $$$0$$$ edges, the code above already handles this. (just increase zero edges and decrease non zero edges properly).