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;

struct node {
    int u , v , w;
    node(){}
    node(int u,int v,int w):
    u(u) , v(v) , w(w){};
    bool operator < (const node &o) const {
        return w < o.w;
    }
};

struct dsu {
    int par[200010];
    void init() {
        for (int i = 1 ; i <= 200000 ; ++i) par[i] = i;
    }
    int fin(int u) {
        if (u != par[u]) par[u] = fin(par[u]);
        return par[u];
    }
    bool join(int u , int v) {
        u = fin(u);
        v = fin(v);
        if (u == v) return false;
        if (par[u] > par[v]) swap(u , v);
        par[u] = v;
        return true;
    }
} a , b;

set < int > vertex;
vector < int > g[200010];
vector < node > edge;
long long rest;

void DFS(int u) {
    vertex.erase(u);
    sort(g[u].begin(),g[u].end());
    int v = 0;
    while (1) {
        auto it = vertex.lower_bound(v);
        if (it == vertex.end()) return;
        v = *it;
        if (!binary_search(g[u].begin(),g[u].end(),v)) {
            a.join(u , v);
            DFS(v);
            rest--;
        }
        v++;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n , m;
    int x = 0;
    cin >> n >> m;
    rest = n * (n - 1) / 2 - m;
    for (int i = 1 ; i <= m ; ++i) {
        int u , v , w;
        cin >> u >> v >> w;
        x ^= w;
        g[u].push_back(v);
        g[v].push_back(u);
        edge.emplace_back(u , v , w);
    }
    a.init();b.init();
    for (int i = 1 ; i <= n ; ++i)
        vertex.insert(i);
    for (int i = 1 ; i <= n ; ++i)
        if (vertex.count(i)) DFS(i);
    if (rest > 0) x = 0;
    int res = 0;
    sort(edge.begin(),edge.end());
    for (auto p : edge) {
        int u = p.u , v = p.v , w = p.w;
        if (a.join(u , v)) {
            res += w;
            b.join(u , v);
        } else if (b.join(u , v)) x = min(x , w);
    }
    cout << res + x;
}
