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;
const int M = 650;
const long long INF = 1e18 + 10010;

int n, m;
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
bool operator<(const Edge &e1, const Edge &e2) {
    return e1.w < e2.w;
}
Edge edg[N];
bool has[M][M];
int d[M][M];
vector<Edge> rem_edg;

long long prim(int ban, int xorr) {
    vector<int> best(n, 0), used(n, 0);
    for (int i = 0; i < rem_edg.size(); ++i) {
        int w = i == ban ? xorr : 0;
        int u = rem_edg[i].u, v = rem_edg[i].v;
        d[u][v] = d[v][u] = w;
    }
    for (int i = 0; i < m; ++i)
        d[edg[i].u][edg[i].v] = d[edg[i].v][edg[i].u] = edg[i].w;
    used[0] = 1;
    long long res = 0;
    for (int it = 0; it < n - 1; ++it) { 
        int id = -1;
        for (int i = 0; i < n; ++i) {
            if (!used[i] && (id == -1 || d[i][best[i]] < d[id][best[id]])) 
                id = i;
        }
        used[id] = 1;
        res += d[id][best[id]];
        for (int i = 0; i < n; ++i) {
            if (!used[i] && d[i][id] < d[i][best[i]])
                best[i] = id;
        }
    }
    return res;
}

void solve_n3() {
    for (int i = 0; i < m; ++i)
        has[edg[i].u][edg[i].v] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (!has[i][j])
                rem_edg.push_back({i, j, 0});
        }
    }
    int xorr = 0;
    for (int i = 0; i < m; ++i)
        xorr ^= edg[i].w;
    long long ans = INF;
    for (int i = 0; i < rem_edg.size(); ++i) 
        ans = min(ans, prim(i, xorr));
    cout << ans << endl;
}

set<int> unused;
set<int> g[N];
int comp[N];

int find_comp(int v) {
    if (comp[v] == v) 
        return v;
    comp[v] = find_comp(comp[v]);
    return comp[v];
}

void dfs(int v, int cmp) {
    comp[v] = cmp;
    unused.erase(v);
    int last = -1;
    while (!unused.empty()) {
        auto it = unused.upper_bound(last);
        if (it == unused.end())
            break;
        int u = *it;
        last = u;
        if (g[v].count(u)) continue;
        dfs(u, cmp);
    }
}

void solve_mlogn() {
    for (int i = 0; i < m; ++i) {
        g[edg[i].u].insert(edg[i].v);
        g[edg[i].v].insert(edg[i].u);
    }
    for (int i = 0; i < n; ++i)
        unused.insert(i);
    while (!unused.empty()) {
        int v = *unused.begin();
        dfs(v, v);
    }
    sort(edg, edg + m);
    long long ans = 0;
    for (int i = 0; i < m; ++i) {
        int u = find_comp(edg[i].u), v = find_comp(edg[i].v);
        if (u != v) {
            ans += edg[i].w;
            comp[u] = v;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> edg[i].u >> edg[i].v >> edg[i].w;
        --edg[i].u;
        --edg[i].v;
        if (edg[i].u > edg[i].v)
            swap(edg[i].u, edg[i].v);
    }
    long long rem = (long long)n * (n - 1) / 2 - m;
    if (rem <= n - 1) {
        //cout << "n3\n";
        solve_n3();
    } else {
        //cout << "mlogn\n";
        solve_mlogn();
    }
    return 0;
}
