Minimum Cost Walk in Weighted Graph

Confirm the cost definition first

A weighted-graph walk can mean shortest sum, minimum bottleneck, or the known variant where a walk's cost is bitwise AND of all edges used and vertices or edges may be revisited. These are different problems. For the AND-with-revisits version, union every edge into connected components and compute the AND of all edge weights in each component. Any two distinct vertices in that component can traverse enough edges to incorporate the component's minimum achievable bit pattern, so every valid query has that component AND; disconnected vertices return -1.

Explain the surprising invariant

Bitwise AND never gains a one when extra edges are added. Since walks may revisit edges, one can visit every useful edge in a connected component while moving between query endpoints, making the component-wide AND attainable. This argument fails if the problem asks for a simple path or sum of weights, so say the assumption aloud. DSU construction is O((n+m) alpha(n)), aggregation is O(m), and queries are O(alpha(n)); space is O(n). Clarify the specified result for a query from a node to itself, which some versions define as zero.