2 0
 6 8
1 4 1
1 5 1
1 6 1
2 4 1
2 5 1
2 6 1
3 5 1
3 6 1
 6 12
1 3 8763000
1 4 8763000
1 5 8763000
1 6 8763000
2 3 8763000
2 4 1
2 5 8763000
2 6 1
3 5 8763000
3 6 8763000
4 5 8763000
4 6 2

0
 0
 8763002

import sys
input = iter(sys.stdin.read().splitlines()).__next__


class UnionFind:  # based on submission 102831279
    def __init__(self, n):
        """ elements are 0, 1, 2, ..., n-1 """
        self.parent = list(range(n))
    
    def find(self, x):
        found = x
        while self.parent[found] != found:
            found = self.parent[found]
        while x != found:
            y = self.parent[x]
            self.parent[x] = found
            x = y
        return found
    
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

def kruskal(graph):
    F = []
    n = len(graph)
    trees = UnionFind(n)
    edges = []
    # n^2lgn is fine!
    for u in range(n):
        for v in range(u+1, n):
            if v not in graph[u]:
                trees.union(u, v)
            else:
                edges.append((graph[u][v], u, v))
    edges.sort()
    first_unincluded = None
    for _, u, v in edges:
        if trees.find(u) != trees.find(v):
            F.append((u, v))
            trees.union(u, v)
        elif not first_unincluded:
            first_unincluded = (u, v)
    return F, first_unincluded

n, m = map(int, input().split())
# only need to assign positive weight to one edge, preferably not on the MST
# if edge (u, v) is taken out, and it used to be in MST, can we just put in min
# bridge thingy in cut graph
graph = {u: {} for u in range(n)}
xor = 0
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
    xor ^= w
# max size of assigned-edges clique is 633
# so n > 633 => there's some free way to connect clique to rest of graph
# => can take minimum
if n > 633:
    MST = []
    for u in range(n):
        if len(graph[u]) == n:
            v = min(graph[u], key=lambda v: graph[u][v])
            MST.append((w, u, v))
            weight += graph[u][v]
    # take out cycles
    uf = UnionFind(n)
    MST.sort()
    ugliness = 0
    for w, u, v in MST:
        if uf.find(u) != uf.find(v):
            ugliness += w
            uf.union(u, v)
    # we can find an unassigned edge outside MST
    print(ugliness)
else:
    MST, first_unincluded = kruskal(graph)
    included_weights = [graph[u].get(v, 0) for u, v in MST]
    if n-1-included_weights.count(0) < n*(n-1)/2-m:
        print(sum(included_weights))
    else:
        print(sum(included_weights) + (min(xor, graph[first_unincluded[0]][first_unincluded[1]]) if first_unincluded else xor))
