human
Write me a Python code to print on one line one integer — the minimum ugliness among all weight assignments with XOR sum equal to 0 given the following:
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](https://en.wikipedia.org/wiki/Bitwise_operation#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](https://en.wikipedia.org/wiki/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 ≤ u < v ≤ n.
such a graph has (n(n-1))/(2) edges.

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

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ min(2 ⋅ 10^5, (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 ≤ u_i, v_i ≤ n, u ≠ v, 1 ≤ 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.

Examples

Input

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

Output

15

Input

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

Output

0

Input

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

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...
Solve the task in PYTHON3.
assistant
#Here is Python code to print on one line one integer — the minimum ugliness among all weight assignments with XOR sum equal to 0.

import sys, os

if os.environ['USERNAME']=='kissz':
    inp=open('in3.txt','r').readline
    def debug(*args):
        print(*args,file=sys.stderr)
else:
    inp=sys.stdin.readline    
    def debug(*args):
        pass

# SCRIPT STARTS HERE

def getp(i):
    L=[]
    while parent[i]>=0:
        L+=[i]
        i=parent[i]
    for j in L:
        parent[j]=i
    return i
    

n,m=map(int,inp().split())
neighbors=[set() for _ in range(n)]
G=[[] for _ in range(n)]
E=[]
xors=0
for _ in range(m):
    u,v,w=map(int,inp().split())
    neighbors[u-1].add(v-1)
    neighbors[v-1].add(u-1)
    E+=[(w,v-1,u-1)]
    xors^=w

s=0
parent=[-1]*n
k=(n*(n-1))//2-m
nodes=set(range(n))
conn=0
for p in range(n):
    if p not in nodes: continue
    nodes.remove(p)
    Q=[p]
    while Q:
        i=Q.pop()
        new_nodes=set()
        for j in nodes:
            if j not in neighbors[i]:
                parent[j]=p
                G[i].append((j,True))
                G[j].append((i,True))
                new_nodes.add(j)
                conn+=1
                debug(i,j,0)
                k-=1   
                Q.append(j)
        nodes-=new_nodes
debug(parent)       
if conn<n-1 or k==0:
    E.sort()
    for w,u,v in E:
        pu=getp(u)
        pv=getp(v)
        if pu!=pv:
            s+=w
            parent[pu]=pv
            G[u].append((v,False))
            G[v].append((u,False))
            conn+=1
            debug(u,v,w)
        elif k==0 and w<xors:
            Q=[(u,False)]
            seen=[False]*n
            seen[u]=True
            while Q:
                i,new=Q.pop()
                for j,new_edge in G[i]:
                    if not seen[j]:
                        seen[j]=True
                        new_edge |= new
                        if j==v:
                            Q=[]
                            break
                        else:
                            Q.append((j,new_edge))
            if new_edge:
                s+=w
                debug('corr ',u,v,w)
                k+=1;  
      ...