The optimal strategy is to make the weight of the graph's actual minimum spanning tree equal to ~0~, and then force Spiderman's algorithm to get "stuck" as many times as possible, such that it's forced to traverse a weight-~1~ edge to the next node on its path (thus increasing the answer by ~1~).

The algorithm can't be stuck on its first iteration, as if the actual minimum spanning tree's weight is ~0~, then there must be at least one weight-~0~ edge incident to the first node. After that, it can be made to be stuck at any given node whenever all nodes adjacent to that node along fixed-weight edges have already been visited. So, our goal is to maximize the number of times this occurs.

The fixed-weight edges form a forest of trees on the graph, which can be handled independently. For now, let's ignore which node will be chosen as the algorithm's starting node, and only focus on which nodes we can force the algorithm to get stuck at. If there's ever an "isolated" node ~a~ (such that all its children have already been visited, and either its parent has been visited or it has no parent), we can get the algorithm to jump to it and immediately be stuck again. Otherwise, we should get the algorithm to jump to a node ~b~ one level up, and then traverse the weight-~0~ edge down to a now-isolated child ~c~ before being stuck again. Decomposing each of the trees into an optimal set of single nodes ~a~ and pairs of nodes ~(b, c)~ as described above can be done in ~\mathcal O(N)~ time by finding each tree and recursively iterating over it, while greedily simulating how the nodes will be split up.

Upon counting the number of nodes at which the algorithm will get stuck in each tree, we can sum these values up, and then subtract ~1~ for the very last node visited by the algorithm (as we will have overcounted it as being stuck after that point). At this point, one thing remains addressed – it matters which node the algorithm starts at, so which one should it be? As mentioned above, the only special thing about the first node is that the algorithm can't get stuck at it. Therefore, if we choose to have started at any node which we weren't forcing the algorithm to get stuck at anyway, then our answer will be unaffected. There will always be at least one such node unless ~M = 0~, in which case we must subtract ~1~ more from our answer.

Note: For those looking for an additional challenge, a more difficult version of this problem is available here.