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;

struct dsu{
    int n;
    vector<int> p;

    dsu(int _n): n(_n){
        p.resize(n + 5);
        iota(p.begin(), p.end(), 0);
    }

    inline int par(int u){
        return p[u] = (u == p[u] ? u : par(p[u]));
    }

    bool unite(int u, int v){
        u = par(u);
        v = par(v);

        if(u == v){
            return 0;
        }

        p[v] = u;
        return 1;
    }
};

constexpr int N = 4e5;
int n, m, p[N], sz[N], cnt[N];
bool jo[N], volt;
vector<pair<int, int> > edges[N];
vector<tuple<int, int, int> > lst;
long long res, mini;

inline int findp(int u){
    return p[u] = (u == p[u] ? u : findp(p[u]));
}

bool uni(int u, int v){
    u = findp(u);
    v = findp(v);

    if(u == v)
        return 0;

    p[v] = u;
    jo[u] |= jo[v];
    sz[u] += sz[v];
    return 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    iota(p, p + N, 0);
    fill(sz, sz + N, 1);

    cin >> n >> m;

    for(int i = 0, u, v; i < m; i++){
        long long w;
        cin >> u >> v >> w;
        edges[u - 1].emplace_back(v - 1, w);
        edges[v - 1].emplace_back(u - 1, w);
        lst.emplace_back(w, u - 1, v - 1);
        mini ^= w;
    }
    queue<int> q;
    for(int i = 0; i < n; i++){
        for(pair<int, int> p : edges[i]){
            int v = findp(p.first);
            cnt[v] = 0;
        }
        for(pair<int, int> p : edges[i]){
            int v = findp(p.first);
            //cout << "el: " << i << ' ' << p.first << ' ' << v << endl;
            cnt[v]++;
        }

        queue<int> tmp;
        while(!q.empty()){
            int id = q.front();

            if(cnt[id] >= sz[id]){
                tmp.push(id);
                //cout << "nagy: " << i << ' ' << id << ' ' << sz[id] << ' ' << cnt[id] << endl;
            }
            else{
                jo[i] = 1;
                if(mini > 0 && cnt[id] < sz[id] - 1){
                    mini = 0;
                }
                //cout << "most: " << id << ' ' << sz[id] << ' ' << cnt[id] << endl;
                uni(i, id);
            }
            cnt[id] = 0;

            q.pop();
        }
        q = tmp;
        q.push(i);
        cnt[i] = 0;
    }

    sort(lst.begin(), lst.end());
    vector<tuple<int, int, int> > comp;
    dsu test(n);

    for(auto xx : lst){
        int w = get<0>(xx), u = get<1>(xx), v = get<2>(xx);

        if(test.unite(u, v))
            comp.emplace_back(w, u, v);
    }

    for(auto xx : comp){
        int w = get<0>(xx), u = get<1>(xx), v = get<2>(xx);
        u = findp(u);
        v = findp(v);
        //cout << "most. " << u << ' ' << v << endl;
        if(u != v){
            uni(u, v);
            res += w;
        }
        else{
            mini = min(1ll*w, mini);
        }
    }

    cout << res + mini << '\n';



}
