CF1508C.Complete the MST

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 \lt 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.

作为一名教师，Riko Hakozaki 经常需要帮助学生解决各学科的问题。今天，她被问到一个编程任务，内容如下：

给定一个包含 $n$ 个节点的无向完全图，其中部分边已被预先赋予正权重，其余边尚未赋权。你需要为所有未赋权的边赋予非负权重，使得最终得到的完全赋权图中，所有边权重的按位异或（XOR）和等于 $0$。

定义一个完全赋权图的丑陋度（ugliness）为该图的最小生成树（MST） 的权重，而生成树的权重等于其所有边的权重之和。你需要为边赋权，使得最终图的丑陋度尽可能小。

需要提醒的是：一个含 $n$ 个节点的无向完全图包含所有满足 $1 \le u \lt v \le n$ 的边 $(u, v)$；这样的图共有 $\frac{n(n-1)}{2}$ 条边。

Riko 不确定如何解决这个问题，因此请你帮她解决。

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 \lt 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.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$0 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2} - 1)$），分别表示节点数和预先指定的边数。输入数据保证至少存在一条未指定的边。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$，$1 \le w_i \lt 2^{30}$），表示从节点 $u_i$ 到节点 $v_i$ 的边已被预先指定权重 $w_i$。任意一条边在输入中至多出现一次。

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

在一行中输出一个整数——所有满足异或和为 $0$ 的权重分配方案中的最小丑陋度。

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.

下图展示了第一个测试用例。黑色权重为题目中预先指定的权重，红色权重由我们分配，蓝色边表示最小生成树。