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;

vector<int> adj[200005], cc[200005];

struct DSU {
    vector<int> lab;
    DSU(int n) {
        lab.assign(n + 1, -1);
    }
    int getRoot(int u) {
        if (lab[u] < 0) return u;
        return lab[u] = getRoot(lab[u]);
    }
    void merge(int u, int v) {
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
    }
};

long long getMST(vector<array<int, 3>> edges, int n) {
    DSU dsu(n);
    long long res = 0;
    for (auto e: edges) {
        int a = dsu.getRoot(e[1]);
        int b = dsu.getRoot(e[2]);
        if (a != b) {
            dsu.merge(a, b);
            res += e[0];
        }
    }
    return res;
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

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

    long long xorAll = 0;
    vector<array<int, 3>> edges;
    set<pair<int, int>> edgeSet;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(v);
        adj[v].push_back(u);
        xorAll ^= w;
        edges.push_back({w, u, v});
        edgeSet.insert(minmax(u, v));
    }

    set<int> unvisited;
    for (int i = 1; i <= n; i++) {
        unvisited.insert(i);
    }

    queue<int> q;

    int numCC = 0;
    for (int i = 1; i <= n; i++) {
        if (unvisited.find(i) != unvisited.end()) {
            unvisited.erase(i);
            numCC++;
            q.push(i);

            while (q.size()) {
                int u = q.front();
                cc[numCC].push_back(u);
                q.pop();

                set<int> notAdj(adj[u].begin(), adj[u].end());

                vector<int> toErase;
                for (auto j: unvisited) {
                    if (notAdj.find(j) == notAdj.end()) {
                        toErase.push_back(j);
                        q.push(j);
                    }
                }
                for (auto j: toErase) unvisited.erase(j);
            }
        }
    }

    long long m1 = n * 1ll * (n - 1) / 2 - m;

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

    if (m1 + numCC != n) {
        vector<array<int, 3>> curEdges;
        for (int i = 1; i <= numCC; i++) {
            for (int j = 0; j + 1 < cc[i].size(); j++) {
                curEdges.push_back({0, cc[i][j], cc[i][j + 1]});
            }
        }
        for (auto l: edges) curEdges.push_back(l);
        long long mst = getMST(curEdges, n);
        cout << mst << endl;
    }
    else {
        vector<array<int, 3>> compEdges;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (edgeSet.find({i, j}) == edgeSet.end()) {
                    compEdges.push_back({0, i, j});
                }
            }
        }
        long long res = 1e18;
        for (auto e: compEdges) {
            long long mst = 0;
            DSU dsu(n);
            for (auto k: compEdges) {
                if (k != e) {
                    int a = dsu.getRoot(k[1]);
                    int b = dsu.getRoot(k[2]);
                    if (a != b) {
                        dsu.merge(a, b);
                    }
                }
            }
            for (auto k: edges) {
                int a = dsu.getRoot(k[1]);
                int b = dsu.getRoot(k[2]);
                if (a != b) {
                    dsu.merge(a, b);
                    mst += k[0];
                }
            }
            res = min(res, mst);
        }

        compEdges.back()[0] = xorAll;
        vector<array<int, 3>> curEdges = compEdges;
        for (auto k: edges) curEdges.push_back(k);

        res = min(res, getMST(curEdges, n));
        cout << res << endl;
    }

    return 0;
}