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 = lambda: sys.stdin.readline().rstrip()


from heapq import heapify, heappush as hpush, heappop as hpop
def dijkstra(n, E, i0=0):
    kk = 18
    mm = (1 << kk) - 1
    h = [i0]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    while h:
        x = hpop(h)
        d, i = x >> kk, x & mm
        # di = hpop(h)
        # d, i = unpack("d", pack("q", (di | mm) - mm))[0], di & mm
        if done[i]: continue
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, (nd << kk) + j)
                    # hpush(h, (unpack("q", pack("d", nd))[0] | mm) - (mm - j))
                    D[j] = nd
    return D
def dijkstra_all(n, E, i0=0):
    kk = 18
    mm = (1 << kk) - 1
    h = [i0]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    while h:
        x = hpop(h)
        d, i = x >> kk, x & mm
        # di = hpop(h)
        # d, i = unpack("d", pack("q", (di | mm) - mm))[0], di & mm
        if done[i]: continue
        done[i] = 1
        for j, w in enumerate(E[i]):
            if j == i: continue
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, (nd << kk) + j)
                    # hpush(h, (unpack("q", pack("d", nd))[0] | mm) - (mm - j))
                    D[j] = nd
    return D
def mst(n, X):
    P = [-1 for i in range(n)]
    def par(a):
        L = []
        while P[a] >= 0:
            L.append(a)
            a = P[a]
        for l in L:
            P[l] = a
        return a
    def unite(a, b):
        if par(a) != par(b):
            if P[par(b)] >= P[par(a)]:
                if P[par(b)] == P[par(a)]: P[par(a)] -= 1
                P[par(b)] = par(a)
            else:
                P[par(a)] = par(b)
 
    c = n - 1
    s = 0
    for i, j, w in sorted(X, key = lambda x: x[2]):
        if par(i) != par(j):
            unite(i, j)
            c -= 1
            s += w
        if not c:
            return(s)
def mst_next(n, X):
    if n <= 1: return 0
    P = [-1 for i in range(n)]
    def par(a):
        L = []
        while P[a] >= 0:
            L.append(a)
            a = P[a]
        for l in L:
            P[l] = a
        return a
    def unite(a, b):
        if par(a) != par(b):
            if P[par(b)] >= P[par(a)]:
                if P[par(b)] == P[par(a)]: P[par(a)] -= 1
                P[par(b)] = par(a)
            else:
                P[par(a)] = par(b)
 
    c = n - 1
    s = 0
    done = 0
    for i, j, w in sorted(X, key = lambda x: x[2]):
        if par(i) != par(j):
            unite(i, j)
            c -= 1
            s += w
        if not c:
            if done:
                if w > 1:
                    return (s, w)
            else:
                done = 1
    
    return (s, 1 << 100)
N, M = map(int, input().split())
if N <= 900:
    MM = N * (N - 1) // 2 - M # Unassigned Edge
    used = [[0] * i for i in range(N)]
    X = []
    mi = 1 << 100
    s = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        mi = min(mi, c)
        s ^= c
        a -= 1
        b -= 1
        if a < b: a, b = b, a
        
        X.append((a, b, c << 10))
        used[a][b] = 1
    for i in range(N):
        ui = used[i]
        for j in range(i):
            if not ui[j]:
                X.append((i, j, 1))

    mc, ne = mst_next(N, X)
    ne >>= 10
    # print("mc, ne, mc>>10", mc, ne, mc >> 10)
    ans = mc >> 10
    c = mc & 1023
    if c == MM:
        ans += min(s, ne)
    print(ans)
else:
    # ttt = 0
    # while 1:
    #     ttt += 1
    C = [0] * N
    Y = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        C[a] += 1
        C[b] += 1
        Y.append((a, b, c))
        # Y[a].append((b, c))
        # Y[b].append((a, c))
    
    # F = []
    DC = {}
    cnt = 0
    for i, c in enumerate(C):
        if c == N - 1:
            # F.append(i)
            cnt += 1
            DC[i] = cnt
    
    X = []
    NN = cnt + 1
    for a, b, c in Y:
        da = DC[a] if a in DC else 0
        db = DC[b] if b in DC else 0
        if da and db:
            X.append((da, db, c))
        elif da:
            X.append((0, da, c))
        elif db:
            X.append((0, db, c))
    
    print(mst(NN, X))