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;

#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

typedef long long ll;
typedef pair<int, int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


struct DSU {
    int n;
    vector<int> par, sz;
 
    DSU(int _size) {
        n = _size;
        par.assign(n, 0);
        iota(all(par), 0);
        sz.assign(n, 1);
    }
    int getPar(int v) {
        if (v == par[v]) return v;
        return par[v] = getPar(par[v]);
    }
    bool uniSet(int u, int v) {
        u = getPar(u);
        v = getPar(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        par[u] = v;
        return true;
    }
};


const int N = (int)2e5 + 5;
 
set<int> g[N];
set<int> notUsed;
int color[N];
 
void dfs(int v, vector<int>& comp, int c) {
    notUsed.erase(v);
    comp.push_back(v);
    color[v] = c;
 
    int x = 0;
    while(!notUsed.empty()) {
        auto it = notUsed.lower_bound(x);
        if (it == notUsed.end()) break;
        x = *it;
        if (g[v].find(x) == g[v].end()) {
            dfs(x, comp, c);
        } else {
            x++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    int XOR = 0;
    vector<pair<int, pii>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        XOR ^= w;
        edges.push_back({w, {u, v}});
        g[u].insert(v);
        g[v].insert(u);
    }
    
    for (int i = 0; i < n; ++i) {
        notUsed.insert(i);
    }
    DSU dsu(n);
    int add = XOR;
    
    int cntComp = 0;
    for (int v = 0; v < n; ++v) {
        if (!notUsed.count(v)) continue;
        vector<int> comp;
        dfs(v, comp, cntComp);
        for (int x : comp) {
            dsu.uniSet(x, v);
        }
        int cnt_edges = 0;
        for (int x : comp) {
            for (int y : g[x]) {
                if (x < y && color[y] == cntComp) ++cnt_edges;
            }
        }
        int szc = sz(comp);
        //cout << szc << ' ' << cnt_edges << '\n';
        if (cnt_edges < (ll)(szc - 1) * szc / 2 - (szc - 1)) {
            add = 0;
        }
        ++cntComp;
    }
    
    sort(all(edges));
    ll ans = 0;
    DSU dsu2(n);
    for (auto [w, pr] : edges) {
        auto [u, v] = pr;
        bool ok = dsu2.uniSet(u, v);
        if (dsu.uniSet(u, v)) {
            ans += w;
        } else if (ok) {
            add = min(add, w);
        }
    }
    ans += add;
    
    cout << ans << '\n';
}