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 MAXN = 200010;
const int INF = (1 << 30) + 5;
int degree[MAXN];
vector<pair<int, int>> adj[MAXN];
set<pair<int, int>> edges;
int from[MAXN], to[MAXN], weg[MAXN];
set<int> unused;
int ncomps = 0;
int comp_belong[MAXN], comp_size[MAXN], comp_edges[MAXN], comp_min[MAXN];
void anti_dfs (int x) {
    comp_belong[x] = ncomps;
    comp_size[ncomps] += 1;
    unused.erase(x);
    vector<int> go;
    for (int to : unused) {
        if (!edges.count({x, to})) go.push_back(to);
    }
    for (int to : go) {
        unused.erase(to);
    }
    for (int to : go) {
        anti_dfs(to);
    }
}
struct dsu {
    vector<int> par;
    dsu (int _n) {
        par.resize(_n + 1);
        iota(par.begin(), par.end(), 0);
    }
    int get (int x) {
        if (par[x] == x) return x;
        return par[x] = get(par[x]);
    }
    bool unite (int x, int y) {
        x = get(x); y = get(y);
        if (x == y) return false;
        if (rand() % 2) swap(x, y);
        par[x] = y;
        return true;
    }
};
inline long long c2 (int x) { return 1ll * x * (x - 1) / 2; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int xor_all = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> from[i] >> to[i] >> weg[i];
        xor_all ^= weg[i];
        edges.insert({from[i], to[i]});
        edges.insert({to[i], from[i]});
    }
    for (int i = 1; i <= n; i++) unused.insert(i);
    for (int i = 1; i <= n; i++) {
        if (!unused.count(i)) continue;
        ncomps += 1;
        anti_dfs(i);
    }
    // cerr << ncomps << " comps" << endl;
    vector<tuple<int, int, int>> id;
    for (int i = 1; i <= ncomps; i++) {
        comp_edges[i] = 0; comp_min[i] = INF;
    }
    for (int i = 1; i <= m; i++) {
        int c1 = comp_belong[from[i]];
        int c2 = comp_belong[to[i]];
        if (c1 == c2) {
            comp_edges[c1] += 1;
            comp_min[c1] = min(comp_min[c1], weg[i]);
        } else {
            id.push_back({weg[i], c1, c2});
        }
    }
    long long ans = 0;
    sort(id.begin(), id.end());
    int smallest = INF;
    dsu d(ncomps);
    for (auto &e : id) {
        // cout << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << endl;
        bool adding = (d.unite(get<1>(e), get<2>(e)));
        if (adding) {
            // cerr << "yeah" << endl;
            ans += get<0>(e);
        } else {
            if (max(comp_size[get<1>(e)], comp_size[get<2>(e)]) > 1) smallest = min(smallest, get<0>(e));
        }
    }
    // cerr << "mst ans " << ans << endl;
    bool dontcare = false;
    for (int i = 1; i <= ncomps; i++) {
        long long most = c2(comp_size[i]);
        if (comp_edges[i] + (comp_size[i] - 1) < most) {
            dontcare = true;
            break;
        }
    }
    if (dontcare) {
        cout << ans << endl;
        return 0;
    }
    for (int i = 1; i <= ncomps; i++) {
        smallest = min(smallest, comp_min[i]);
    }
    // assert(smallest < INF);
    smallest = min(smallest, xor_all);
    cout << ans + smallest << endl;
    return 0;
}