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 = 2e5+7;
struct DSU {
    int rep[N], sz[N];
    vector<int> ops;

    void init() {
        for (int i=0; i<N; i++)
            rep[i] = i, sz[i] = 1;
    }

    int find(int u) {
        while(rep[u] != u)  u = rep[u];
        return u;
    }

    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)   return false;

        if (sz[u] < sz[v])    swap(u, v);
        rep[v] = u;
        sz[u] += sz[v];

        return true;
    }
};

struct Edge {
    int u, v, w;
};
vector<Edge> edges;
bool in[N];

set<int> adj[N];
set<int> unvisited;
bool vis[N];
DSU zero;
bool zerocycle = false;
int ee = 0;

void dfs(int u) {
//    cout<<"At "<<u<<endl;
    assert(!vis[u]);
    vis[u] = 1;
    unvisited.erase(u);

    for (auto it = unvisited.begin(); it != unvisited.end(); ) {
        int v = *it;
        if (adj[u].count(v))    {
            it++;
            continue;
        }
        if (zero.merge(u, v))  ee++;
        dfs(v);
        it = unvisited.upper_bound(v);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin>>n>>m;

    long long xoor = 0, un = 1LL*n*(n-1)/2 - m;
    for (int i=1; i<=m; i++) {
        int u, v, w;
        cin>>u>>v>>w;
        adj[u].insert(v);
        adj[v].insert(u);
        edges.push_back({u, v, w});
        xoor ^= w;
    }

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {return a.w < b.w;});
    for (int i=1; i<=n; i++)    unvisited.insert(i);

    zero.init();
    for (int i=1; i<=n; i++) {
        if (vis[i]) continue;
        dfs(i);
    }

    long long ans = 0;
    DSU ww;
    ww.init();
    for (int i=0; i<edges.size(); i++) {
        Edge e = edges[i];
        if (zero.merge(e.u, e.v))   {
            ans += e.w;
            in[i] = 1;
            ww.merge(e.u, e.v);
        }
    }


    if (ee < un) {
        cout<<ans<<endl;
    }
    else {
        int add = xoor;

        for (int i=0; i<edges.size(); i++) {
            Edge e = edges[i];
            if (ww.find(e.u) != ww.find(e.v)) {
                add = min(add, e.w);
            }
        }

        cout<<ans+add<<endl;
    }
}
