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;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    vector<unordered_set<int>> ed(n);
    int val = 0;
    vector<pair<int, pair<int,int>>> edges;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        edges.push_back({w, {u, v}});
        ed[u].insert(v);
        ed[v].insert(u);
        val ^= w;
    }

    unordered_set<int> visited;
    unordered_set<int> not_visited;
    for(int i = 0; i < n; i++) not_visited.insert(i);

    pair<int,int> good_edge = make_pair(-1, -1);

    for(int i = 0; i < n; i++) {
        if(visited.find(i) != visited.end()) continue;
        visited.insert(i);
        not_visited.erase(i);
        queue<pair<int,int>> q;
        q.push({i, i});
        while(!q.empty()) {
            pair<int,int> now = q.front();
            q.pop();
            vector<int> go;
            go.reserve(10);
            for(int x : not_visited) {
                if(ed[now.first].find(x) == ed[now.first].end()) {
                    q.push({x, now.first});
                    go.push_back(x);
                }
            }
            for(int x : visited) {
                // there is some cycle here
                if(x != now.first && x != now.second && ed[now.first].find(x) == ed[now.first].end()) {
                    good_edge = make_pair(now.first, x);
                }
            }
            for(int x : go) {
                visited.insert(x);
                not_visited.erase(x);
            }
        }
    }
    if(good_edge.first == -1) {
        for(int i = 0; i < n; i++) {
            bool f = false;
            for(int j = i + 1; j < n; j++) {
                if(ed[i].find(j) == ed[i].end()) {
                    good_edge = make_pair(i, j);
                    f = true;
                    break;
                }
            }
            if(f) break;
        }
    }

    visited.clear();
    not_visited.clear();
    for(int i = 0; i < n; i++) not_visited.insert(i);

    ed[good_edge.first].insert(good_edge.second);
    ed[good_edge.second].insert(good_edge.first);


    edges.push_back({val, good_edge});

    vector<int> dsu(n);
    for(int i = 0; i < n; i++) dsu[i] = i;

    auto find_parent = [&](auto Self, int u) -> int {
        if(dsu[u] == u) return u;
        return dsu[u] = Self(Self, dsu[u]);
    } ;

    auto merge = [&](int u, int v) {
        u = find_parent(find_parent, u);
        v = find_parent(find_parent, v);
        dsu[u] = v;
    };

    for(int i = 0; i < n; i++) {
        if(visited.find(i) != visited.end()) continue;
        visited.insert(i);
        not_visited.erase(i);
        queue<pair<int,int>> q;
        q.push({i, i});
        while(!q.empty()) {
            pair<int,int> now = q.front();
            q.pop();
            vector<int> go;
            go.reserve(10);
            for(int x : not_visited) {
                if(ed[now.first].find(x) == ed[now.first].end()) {
                    q.push({x, now.first});
                    go.push_back(x);
                }
            }
            for(int x : go) {
                merge(x, now.first);
                visited.insert(x);
                not_visited.erase(x);
            }
        }
    }

    sort(edges.begin(), edges.end());

    ll ans = 0;

    for(auto x : edges) {
        if(find_parent(find_parent, x.second.first) != find_parent(find_parent, x.second.second)) {
            ans += x.first;
            merge(x.second.first, x.second.second);
        }
    }

    cout << ans;


    return 0;
}