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

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef long long LL;

set<int> remain, out[N];

int vis[N], n; vector<int> p;

void dfs(int u) {
    vis[u] = 1, p.push_back(u), remain.erase(u);
    out[u].insert(n + 1);
    int lst = 0;
    for (auto v : out[u]) {
        while (233) {
            auto t = remain.lower_bound(v);
            if (t == remain.begin()) break;
            t--;
            if (*t <= lst) break;
            dfs(*t);
        }
        lst = v;
    }
}

int fa[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int from[N], to[N], w[N], tA[N], tB[N], tot, id[N], fuck[N];

int A[N], B[N], C[N], ct[N], sz[N];

int main() {
    int m, sum = 0; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) remain.insert(i), fa[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &A[i], &B[i], &C[i]), sum ^= C[i];
        out[A[i]].insert(B[i]), out[B[i]].insert(A[i]);
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        p.clear(), dfs(i);
        for (auto t : p) fa[find(t)] = find(i);
        sz[find(i)] = p.size();
    }
    int mn = 2e9;
    for (int i = 1; i <= m; i++) {
        int a = find(A[i]), b = find(B[i]);
        if (a == b) ct[a]++, mn = min(mn, C[i]);
        else tot++, from[tot] = a, to[tot] = b, w[tot] = C[i], tA[tot] = A[i], tB[tot] = B[i];
    } 
    bool flag = false;
    for (int i = 1; i <= n; i++) if (i == fa[i]) {
        LL t = (LL)sz[i] * (sz[i] - 1) / 2;
        if (t - ct[i] >= sz[i]) flag = true;
    }
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= tot; i++) id[i] = i;
    sort(id + 1, id + tot + 1, [&](int a, int b) {
        return w[a] < w[b];
    });
    LL res = 0;
    for (int i = 1; i <= tot; i++) {
        int u = find(from[id[i]]), v = find(to[id[i]]);
        if (u != v) fa[find(u)] = v, res += w[id[i]], fuck[id[i]] = 1;
    }
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= tot; i++) if (fuck[i]) 
        fa[find(tA[i])] = find(tB[i]);
    for (int i = 1; i <= tot; i++) if (!fuck[i]) {
        if (find(tA[i]) != find(tB[i])) mn = min(mn, w[i]);
    }
    if (!flag) res += min(sum, mn);
    printf("%lld\n", res);
}