Complete the MST

Description:

Input:

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:

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

Sample Input:

4 4
2 1 14
1 4 14
3 2 15
4 3 8

Sample Output:

15

Sample Input:

6 6
3 6 4
2 4 1
4 5 7
3 4 10
3 5 1
5 2 15

Sample Output:

0

Sample Input:

5 6
2 3 11
5 3 7
1 4 10
2 4 14
4 3 8
2 5 6

Sample Output:

6

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.