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 < 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.
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.  
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.
Print on one line one integer  — the minimum ugliness among all weight assignments with XOR sum equal to $$$0$$$.
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (n + 1) + v

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]
(n, m) = map(int, input().split())
inf = pow(10, 15) + 1
if n <= 700:
    n2 = (n + 1) * (n + 1)
    x = [0] * n2
    d = defaultdict(lambda : [])
    s = set()
    z = 0
    for _ in range(m):
        (u, v, w) = map(int, input().split())
        if u > v:
            (u, v) = (v, u)
        x[f(u, v)] = w
        d[w].append((u, v))
        s.add(w)
        z ^= w
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    size = [1 for _ in range(n + 1)]
    f0 = 0
    e = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if not x[f(i, j)]:
                e.append((i, j))
                if same(i, j):
                    f0 = 1
                else:
                    unite(i, j)
    if f0 or not z or (not len(e)):
        s = list(s)
        s.sort()
        ans = 0
        for w in s:
            for (u, v) in d[w]:
                if not same(u, v):
                    ans += w
                    unite(u, v)
    elif len(e) == 1:
        s.add(z)
        s = list(s)
        s.sort()
        d[z].append(e[0])
        root = [i for i in range(n + 1)]
        rank = [1 for _ in range(n + 1)]
        size = [1 for _ in range(n + 1)]
        ans = 0
        for w in s:
            for (u, v) in d[w]:
                if not same(u, v):
                    ans += w
                    unite(u, v)
    else:
        s.add(z)
        s = list(s)
        s.sort()
        d[z].append((0, 0))
        ans = inf
        for (u, v) in e:
            d[z][-1] = (u, v)
            root = [i for i in range(n + 1)]
            rank = [1 for _ in range(n + 1)]
            size = [1 for _ in range(n + 1)]
            for (i, j) in e:
                if u ^ i or v ^ j:
                    unite(i, j)
            ans0 = 0
            c = n - len(e)
            for w in s:
                for (i, j) in d[w]:
                    if not same(i, j):
                        c -= 1
                        ans0 += w
                        unite(i, j)
                    if not c:
                        break
                if not c:
                    break
            ans = min(ans, ans0)
else:
    G = [[] for _ in range(n + 1)]
    d = defaultdict(lambda : [])
    s = set()
    for _ in range(m):
        (u, v, w) = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
        d[w].append((u, v))
        s.add(w)
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    size = [1 for _ in range(n + 1)]
    now = set([i for i in range(1, n + 1)])
    for i in range(1, n + 1):
        if not i in now:
            continue
        now.remove(i)
        (q, k) = ([i], 0)
        while len(q) ^ k:
            u = q[k]
            ns = set()
            for v in G[u]:
                if v in now:
                    ns.add(v)
                    now.remove(v)
            for v in now:
                q.append(v)
            now = ns
            k += 1
        for j in q:
            unite(i, j)
    s = list(s)
    s.sort()
    ans = 0
    for w in s:
        for (u, v) in d[w]:
            if not same(u, v):
                ans += w
                unite(u, v)
print(ans)
def divisors(M):
    d = []
    i = 1
    while M >= i ** 2:
        if M % i == 0:
            d.append(i)
            if i ** 2 != M:
                d.append(M // i)
        i = i + 1
    return d

def popcount(x):
    x = x - (x >> 1 & 1431655765)
    x = (x & 858993459) + (x >> 2 & 858993459)
    x = x + (x >> 4) & 252645135
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 127

def eratosthenes(n):
    res = [0 for i in range(n + 1)]
    prime = set([])
    for i in range(2, n + 1):
        if not res[i]:
            prime.add(i)
            for j in range(1, n // i + 1):
                res[i * j] = 1
    return prime

def factorization(n):
    res = []
    for p in prime:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res.append(p)
    if n != 1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2, n + 1):
        if x ** 2 > n:
            break
        if n % x == 0:
            res = res // x * (x - 1)
            while n % x == 0:
                n //= x
    if n != 1:
        res = res // n * (n - 1)
    return res

def ind(b, n):
    res = 0
    while n % b == 0:
        res += 1
        n //= b
    return res

def isPrimeMR(n):
    if n == 1:
        return 0
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1

def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        (y, r, q, g) = (2, 1, 1, 1)
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)

def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    (ret[n], n) = (1, 1)
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p] + 1):
                newres.append(d * p ** j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    elif num == 2:
        return 3
    elif num == 3:
        return 0
    else:
        x = baseorder(num)
        return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
    if n == 0:
        res = [X[0] * Y[0] % mod]
        return res
    x = [digit[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    z = [digit[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    res1 = xorconv(n - 1, x, y)
    res2 = xorconv(n - 1, z, w)
    former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
    latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
    former = list(map(lambda x: x % mod, former))
    latter = list(map(lambda x: x % mod, latter))
    return former + latter

def merge_sort(A, B):
    (pos_A, pos_B) = (0, 0)
    (n, m) = (len(A), len(B))
    res = []
    while pos_A < n and pos_B < m:
        (a, b) = (A[pos_A], B[pos_B])
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize:

    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x:
            return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]] != stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy:
            return
        self.group -= 1
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.val = [0 for i in range(N)]
        self.flag = True
        self.edge = [[] for i in range(N)]

    def dfs(self, v, pv):
        stack = [(v, pv)]
        new_parent = self.parent[pv]
        while stack:
            (v, pv) = stack.pop()
            self.parent[v] = new_parent
            for (nv, w) in self.edge[v]:
                if nv != pv:
                    self.val[nv] = self.val[v] + w
                    stack.append((nv, v))

    def unite(self, x, y, w):
        if not self.flag:
            return
        if self.parent[x] == self.parent[y]:
            self.flag = self.val[x] - self.val[y] == w
            return
        if self.size[self.parent[x]] > self.size[self.parent[y]]:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[x] += self.size[y]
            self.val[y] = self.val[x] - w
            self.dfs(y, x)
        else:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[y] += self.size[x]
            self.val[x] = self.val[y] + w
            self.dfs(x, y)

class Dijkstra:

    class Edge:

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add_edge(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10 ** 15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))
        while len(que) != 0:
            (cost, v) = heapq.heappop(que)
            if d[v] < cost:
                continue
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0] * N
    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z_alg[k] < j:
            Z_alg[i + k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

class BIT:

    def __init__(self, n, mod=0):
        self.BIT = [0] * (n + 1)
        self.num = n
        self.mod = mod

    def query(self, idx):
        res_sum = 0
        mod = self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            if mod:
                res_sum %= mod
            idx -= idx & -idx
        return res_sum

    def update(self, idx, x):
        mod = self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            if mod:
                self.BIT[idx] %= mod
            idx += idx & -idx
        return

class dancinglink:

    def __init__(self, n, debug=False):
        self.n = n
        self.debug = debug
        self._left = [i - 1 for i in range(n)]
        self._right = [i + 1 for i in range(n)]
        self.exist = [True for i in range(n)]

    def pop(self, k):
        if self.debug:
            assert self.exist[k]
        L = self._left[k]
        R = self._right[k]
        if L != -1:
            if R != self.n:
                (self._right[L], self._left[R]) = (R, L)
            else:
                self._right[L] = self.n
        elif R != self.n:
            self._left[R] = -1
        self.exist[k] = False

    def left(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._left[res]
            if res == -1:
                break
            k -= 1
        return res

    def right(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._right[res]
            if res == self.n:
                break
            k -= 1
        return res

class SparseTable:

    def __init__(self, A, merge_func, ide_ele):
        N = len(A)
        n = N.bit_length()
        self.table = [[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func = merge_func
        for i in range(N):
            self.table[i][0] = A[i]
        for j in range(1, n):
            for i in range(0, N - 2 ** j + 1):
                f = self.table[i][j - 1]
                s = self.table[i + 2 ** (j - 1)][j - 1]
                self.table[i][j] = self.merge_func(f, s)

    def query(self, s, t):
        b = t - s + 1
        m = b.bit_length() - 1
        return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

    class node:

        def __init__(self, val):
            self.left = None
            self.right = None
            self.max = val

    def __init__(self):
        self.root = self.node(-10 ** 15)

    def append(self, key, val):
        pos = self.root
        for i in range(29, -1, -1):
            pos.max = max(pos.max, val)
            if key >> i & 1:
                if pos.right is None:
                    pos.right = self.node(val)
                    pos = pos.right
                else:
                    pos = pos.right
            elif pos.left is None:
                pos.left = self.node(val)
                pos = pos.left
            else:
                pos = pos.left
        pos.max = max(pos.max, val)

    def search(self, M, xor):
        res = -10 ** 15
        pos = self.root
        for i in range(29, -1, -1):
            if pos is None:
                break
            if M >> i & 1:
                if xor >> i & 1:
                    if pos.right:
                        res = max(res, pos.right.max)
                    pos = pos.left
                else:
                    if pos.left:
                        res = max(res, pos.left.max)
                    pos = pos.right
            elif xor >> i & 1:
                pos = pos.right
            else:
                pos = pos.left
        if pos:
            res = max(res, pos.max)
        return res

def solveequation(edge, ans, n, m):
    x = [0] * m
    used = [False] * n
    for v in range(n):
        if used[v]:
            continue
        y = dfs(v)
        if y != 0:
            return False
    return x

    def dfs(v):
        used[v] = True
        r = ans[v]
        for (to, dire, id) in edge[v]:
            if used[to]:
                continue
            y = dfs(to)
            if dire == -1:
                x[id] = y
            else:
                x[id] = -y
            r += y
        return r

class Matrix:
    mod = 10 ** 9 + 7

    def set_mod(m):
        Matrix.mod = m

    def __init__(self, L):
        self.row = len(L)
        self.column = len(L[0])
        self._matrix = L
        for i in range(self.row):
            for j in range(self.column):
                self._matridigit[i][j] %= Matrix.mod

    def __getitem__(self, item):
        if type(item) == int:
            raise IndexError('you must specific row and column')
        elif len(item) != 2:
            raise IndexError('you must specific row and column')
        (i, j) = item
        return self._matridigit[i][j]

    def __setitem__(self, item, val):
        if type(item) == int:
            raise IndexError('you must specific row and column')
        elif len(item) != 2:
            raise IndexError('you must specific row and column')
        (i, j) = item
        self._matridigit[i][j] = val

    def __add__(self, other):
        if (self.row, self.column) != (other.row, other.column):
            raise SizeError('sizes of matrixes are different')
        res = [[0 for j in range(self.column)] for i in range(self.row)]
        for i in range(self.row):
            for j in range(self.column):
                res[i][j] = self._matridigit[i][j] + other._matridigit[i][j]
                res[i][j] %= Matrix.mod
        return Matrix(res)

    def __sub__(self, other):
        if (self.row, self.column) != (other.row, other.column):
            raise SizeError('sizes of matrixes are different')
        res = [[0 for j in range(self.column)] for i in range(self.row)]
        for i in range(self.row):
            for j in range(self.column):
                res[i][j] = self._matridigit[i][j] - other._matridigit[i][j]
                res[i][j] %= Matrix.mod
        return Matrix(res)

    def __mul__(self, other):
        if type(other) != int:
            if self.column != other.row:
                raise SizeError('sizes of matrixes are different')
            res = [[0 for j in range(other.column)] for i in range(self.row)]
            for i in range(self.row):
                for j in range(other.column):
                    temp = 0
                    for k in range(self.column):
                        temp += self._matridigit[i][k] * other._matrix[k][j]
                    res[i][j] = temp % Matrix.mod
            return Matrix(res)
        else:
            n = other
            res = [[n * self._matridigit[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
            return Matrix(res)

    def __pow__(self, m):
        if self.column != self.row:
            raise MatrixPowError('the size of row must be the same as that of column')
        n = self.row
        res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
        while m:
            if m % 2 == 1:
                res = res * self
            self = self * self
            m //= 2
        return res

    def __str__(self):
        res = []
        for i in range(self.row):
            for j in range(self.column):
                res.append(str(self._matridigit[i][j]))
                res.append(' ')
            res.append('\n')
        res = res[:len(res) - 1]
        return ''.join(res)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, m) = mi()
edge = [set([]) for i in range(n)]
E = []
xor = 0
for _ in range(m):
    (u, v, c) = mi()
    edge[u - 1].add(v - 1)
    edge[v - 1].add(u - 1)
    E.append((u - 1, v - 1, c))
    xor ^= c
visited = [False for i in range(n)]
rest = [i for i in range(n)]
group = []
root = []
parent = [-1 for v in range(n)]
for v in range(n):
    if not visited[v]:
        g = set([v])
        root.append(v)
        visited[v] = True
        stack = [v]
        parent[v] = v
        while stack:
            u = stack.pop()
            for nv in rest:
                if nv == v:
                    continue
                if nv not in edge[u] and (not visited[nv]):
                    visited[nv] = True
                    g.add(nv)
                    stack.append(nv)
                    parent[nv] = v
            rest = [nv for nv in rest if not visited[nv]]
        group.append(g)
uf = UnionFindVerSize(n)
G = len(group)
for i in range(G):
    p = root[i]
    for v in group[i]:
        uf.unite(p, v)
E.sort(key=lambda x: x[2])
alt = []
use = []
res = xor
for (u, v, c) in E:
    if not uf.is_same_group(u, v):
        res += c
        uf.unite(u, v)
        use.append((u, v))
    else:
        alt.append((u, v, c))
flag = True
for i in range(G):
    size = len(group[i])
    edge_cnt = size * (size - 1)
    for v in group[i]:
        for nv in edge[v]:
            if nv in group[i]:
                edge_cnt -= 1
    if edge_cnt // 2 != size - 1:
        flag = False
base = res - xor
if not flag:
    print(base)
else:
    tree = [[] for i in range(n)]
    for i in range(G):
        size = len(group[i])
        edge_cnt = size * (size - 1)
        for v in group[i]:
            for nv in group[i]:
                if nv not in edge[v] and nv != v:
                    tree[v].append((nv, 1))
    for (u, v) in use:
        tree[u].append((v, 0))
        tree[v].append((u, 0))
    deq = deque([0])
    cnt = [0 for i in range(n)]
    tree_parent = [-1 for v in range(n)]
    depth = [0 for i in range(n)]
    while deq:
        v = deq.popleft()
        for (nv, c) in tree[v]:
            if tree_parent[nv] == -1 and nv:
                tree_parent[nv] = v
                depth[nv] = depth[v] + 1
                cnt[nv] = cnt[v] + c
                deq.append(nv)
    N = n
    LV = (N - 1).bit_length()

    def construct(prv):
        kprv = [prv]
        S = prv
        for k in range(LV):
            T = [0] * N
            for i in range(N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            kprv.append(T)
            S = T
        return kprv
    kprv = construct(tree_parent)

    def lca(u, v):
        dd = depth[v] - depth[u]
        if dd < 0:
            (u, v) = (v, u)
            dd = -dd
        for k in range(LV + 1):
            if dd & 1:
                v = kprv[k][v]
            dd >>= 1
        if u == v:
            return u
        for k in range(LV - 1, -1, -1):
            pu = kprv[k][u]
            pv = kprv[k][v]
            if pu != pv:
                u = pu
                v = pv
        return kprv[0][u]
    plus = xor
    for (u, v, c) in alt:
        L = lca(u, v)
        t = cnt[u] + cnt[v] - 2 * cnt[L]
        assert t >= 0
        if parent[u] == parent[v]:
            assert t
        if t:
            plus = min(plus, c)
    print(base + plus)
import sys
from sys import stdin
from collections import deque

def uf_find(n, p):
    ufl = []
    while p[n] != n:
        ufl.append(n)
        n = p[n]
    for i in ufl:
        p[i] = n
    return n

def uf_union(a, b, p, rank):
    ap = uf_find(a, p)
    bp = uf_find(b, p)
    if ap == bp:
        return True
    else:
        if rank[ap] > rank[bp]:
            p[bp] = ap
        elif rank[ap] < rank[bp]:
            p[ap] = bp
        else:
            p[bp] = ap
            rank[ap] += 1
        return False
(n, m) = map(int, stdin.readline().split())
if n <= 1000:
    lis = [[0] * n for i in range(n)]
    wuv = []
    XOR = 0
    for i in range(m):
        (u, v, w) = map(int, stdin.readline().split())
        u -= 1
        v -= 1
        wuv.append((w, u, v))
        lis[u][v] = lis[v][u] = w
        XOR ^= w
    wuv.sort()
    p = [i for i in range(n)]
    rank = [0] * n
    edge = []
    flag = False
    for i in range(n):
        for j in range(i):
            if lis[i][j] == 0:
                if uf_union(i, j, p, rank):
                    flag = True
                else:
                    edge.append((i, j, 0))
    nans = 0
    for (w, u, v) in wuv:
        if uf_union(u, v, p, rank):
            pass
        else:
            nans += w
            edge.append((u, v, w))
    if flag:
        print(nans)
        sys.exit()
    p = [i for i in range(n)]
    rank = [0] * n
    for (i, j, w) in edge:
        if w > 0:
            uf_union(i, j, p, rank)
    nplus = XOR
    for (w, u, v) in wuv:
        if uf_find(u, p) != uf_find(v, p):
            nplus = min(nplus, w)
            break
        elif w > nplus:
            break
    print(nans + nplus)
else:
    lis = [[] for i in range(n)]
    wuv = []
    for i in range(m):
        (u, v, w) = map(int, stdin.readline().split())
        u -= 1
        v -= 1
        wuv.append((w, u, v))
        lis[u].append((v, w))
        lis[v].append((u, w))
    able = [True] * n
    p = [i for i in range(n)]
    rank = [0] * n
    for st in range(n):
        if not able[st]:
            continue
        block = [0] * n
        cnt = 0
        able[st] = False
        q = deque([st])
        while q:
            while q:
                nv = q.popleft()
                cnt += 1
                for (u, w) in lis[nv]:
                    if able[u] and block[u] == cnt - 1:
                        block[u] = cnt
            for i in range(n):
                if able[i] and block[i] != cnt:
                    uf_union(i, st, p, rank)
                    able[i] = False
                    q.append(i)
    wuv.sort()
    ans = 0
    for (w, u, v) in wuv:
        if not uf_union(u, v, p, rank):
            ans += w
    print(ans)