Complete the MST
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 2500
Tags: bitmasks, brute force, data structures, dfs and similar, dsu, graphs, greedy, trees

As a teacher, Riko Hakozaki often needs to help her students with problems from various subjects. Today, she is asked a programming task which goes as follows.

You are given an undirected complete graph with $$$n$$$ nodes, where some edges are pre-assigned with a positive weight while the rest aren't. You need to assign all unassigned edges with non-negative weights so that in the resulting fully-assigned complete graph the XOR sum of all weights would be equal to $$$0$$$.

Define the ugliness of a fully-assigned complete graph the weight of its minimum spanning tree, where the weight of a spanning tree equals the sum of weights of its edges. You need to assign the weights so that the ugliness of the resulting graph is as small as possible.

As a reminder, an undirected complete graph with $$$n$$$ nodes contains all edges $$$(u, v)$$$ with $$$1 \le u < v \le n$$$; such a graph has $$$\frac{n(n-1)}{2}$$$ edges.

She is not sure how to solve this problem, so she asks you to solve it for her.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2} - 1)$$$)  — the number of nodes and the number of pre-assigned edges. The inputs are given so that there is at least one unassigned edge.

The $$$i$$$-th of the following $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u \ne v$$$, $$$1 \le w_i < 2^{30}$$$), representing the edge from $$$u_i$$$ to $$$v_i$$$ has been pre-assigned with the weight $$$w_i$$$. No edge appears in the input more than once.

Output format:
Print on one line one integer  — the minimum ugliness among all weight assignments with XOR sum equal to $$$0$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The following image showcases the first test case. The black weights are pre-assigned from the statement, the red weights are assigned by us, and the minimum spanning tree is denoted by the blue edges.

Example input:
4 4
2 1 14
1 4 14
3 2 15
4 3 8

Example output:
15

Example input:
6 6
3 6 4
2 4 1
4 5 7
3 4 10
3 5 1
5 2 15

Example output:
0

Editorial:
Call $$$x$$$ the XOR sum of the weights of all pre-assigned edges.
Lemma. All but one unassigned edges are assigned with $$$0$$$, while the remaining unassigned edge is assigned with $$$x$$$.
Proof. Consider any assignment of unassigned edges. There are two cases on the minimum spanning tree:
• The MST does not use all unassigned edges: We can assign one unused unassigned edge with $$$x$$$, while all other unassigned edges (including all used in the MST) are assigned with $$$0$$$. This reduces the weight of the MST.
• The MST uses all unassigned edges: We can prove that the sum of weights of unassigned edges is at least $$$x$$$, and the equality can be achieved with the construction from the lemma. Intuitively, the XOR sum is an "uncarried" summation, and the construction from the lemma removes any digit carry.
Let's DFS on the unassigned edges. It can happen that the unassigned edges may separate the graph into multiple components, and we might need to use some pre-assigned edges in our MST. I will divide the collection of pre-assigned edges into 3 types:
1. Edges that must be included in the MST: these are edges with smallest weights that connect the components after traversing through unassigned edges.
2. Edges that cannot be included in the MST: these are edges that form cycles with smaller-weighted pre-assigned edges. In other words, these are edges that do not exist in the minimum spanning forest of the pre-assigned edges.
3. Edges that are in neither of the previous types.
For the unassigned edges, there are two cases:
• The unassigned edges form at least a cycle: We can assign any edge on this cycle as $$$x$$$, the rest as $$$0$$$, then build an MST using the $$$0$$$-weighted edges with pre-assigned edges of type 1.
• The unassigned edges does not form a cycle. Suppose we build the tree using only unassigned edges and edges of type 1. Then any edge of type 3 can replace an unassigned edge in the tree. That is because the edges of type 3 must form a cycle with edges of type 1 and unassigned edges (else it would either be in type 1 or type 2). We can simply replace an unassigned edge in that cycle with this type 3 edge. Therefore, for this case, our solution is to first form the tree with all edges of type 1 and unassigned edge. Then, if the smallest weighted type 3 edge has weight $$$< x$$$, we can replace an unassigned edge with this edge; else, we keep the tree.