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 MN = 2e5+5, MS = 1005;
typedef pair<int,int> pii;
#define F first
#define S second

int N, M, deg[MN]{}, xs = 0; set<pii> adjlp[MN], adjlw[MN];
unordered_set<int> nonzero; bool vis[MN]{};
// nonzero: if a {0,u} is in q, vis: if we have taken {x, u} out of q
priority_queue<pii, vector<pii>, greater<pii> > pq;
long long ans = 0;

bool check(){
    for(int i = 2; i <= N; i++){
        nonzero.insert(i);
    } pq.push({0,1});
    int zeroedges = 0;
    while(!pq.empty()){
        pii pi = pq.top(); pq.pop();
        int u = pi.S; 
        if(vis[u]) continue;
        vis[u] = 1;
        ans += pi.F;
        nonzero.erase(u);

        // printf("%d %d\n", u, pi.F);
        
        for(auto it = nonzero.begin(); it != nonzero.end(); ){
            int v = *it; assert(!vis[v]);
            auto it2 = adjlp[u].lower_bound({v, 0});
            if(it2 == adjlp[u].end() || it2->F != v){
                // printf("%d %d\n", u, v);

                pq.push({0,v});
                zeroedges++;
                it = nonzero.erase(it);
            } else it++;
        }
        for(pii pi2: adjlw[u]){
            pq.push(pi2);
        }
    }
    long long totzero = (long long)N * (N-1) / 2 - M;
    assert(zeroedges <= totzero);
    return zeroedges < totzero;
}

// ================================================

vector<pair<int,pii> > kedges; map<int,int> kused;
int par[MS], rnk[MS];

int top(int u){
    if(par[u] == u) return u;
    return par[u] = top(par[u]);
}

bool merge(int a, int b){
    a = top(a); b = top(b);
    if(a == b) return 0;
    if(rnk[a] > rnk[b]) par[b] = a;
    else par[a] = b, rnk[b] += rnk[a] == rnk[b];
    return 1;
}

void solve(){
    if(!xs){
        printf("%lld\n", ans); return;
    }

    assert(N < MS);

    for(int i = 1; i <= N; i++){
        for(int j = 1; j < i; j++){
            auto it = adjlp[i].lower_bound({j,0});
            kedges.push_back({
                (it == adjlp[i].end() || it->F != j ? 0 : it->S), 
                {i, j}
            });
        }
    }

    sort(kedges.begin(), kedges.end());
    memset(rnk, 0, sizeof(rnk));
    iota(par, par+N+5, 0);

    for(int i = 0; i < kedges.size(); i++){
        int u = kedges[i].S.F, v = kedges[i].S.S, &w = kedges[i].F;
        if(merge(u, v)){
            kused[w]++;
        }
        if(!w) w = xs;
    }

    sort(kedges.begin(), kedges.end());
    memset(rnk, 0, sizeof(rnk));
    iota(par, par+N+5, 0);

    for(int i = 0; i < kedges.size(); i++){
        int u = kedges[i].S.F, v = kedges[i].S.S, w = kedges[i].F;
        assert(w <= xs);
        if(merge(u, v) && !kused[w]--){
            printf("%lld\n", ans + w);
            return;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> M;
    fill(deg, deg+N, N-1);
    for(int i = 0, u, v, w; i < M; i++){
        cin >> u >> v >> w;
        deg[u]--; deg[v]--; xs ^= w;
        adjlp[u].insert({v, w});
        adjlp[v].insert({u, w});
        adjlw[u].insert({w, v});
        adjlw[v].insert({w, u});
    }

    // for(pii pi: adjlw[1]){
    //     printf("%d %d\n", pi.F, pi.S);
    // } printf("\n");

    if(check()){
        printf("%lld\n", ans); return 0;
    }

    // ================================================

    solve();

    return 0;
}