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;

#define f first
#define s second
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define pb push_back

#define vi vector<int>
#define ll long long

const int N = 1e6 + 6;
const int INF = 1e9 + 7;
const ll BIG_ING = 2e18;

vector<map<int, int> > G(N);

ll mst = 0;

int vis[N];
set<int> nieobecne;
vector<int> do_odw = {1};
set<pair<int, pair<int, int> > > kandydaci;

vector<vector<int> > MST(N);
vector<pair<int, int> > MST_kraw;

int rep[N];

int Find(int x){
    return x == rep[x] ? x : rep[x] = Find(rep[x]);
}

void Union(int a, int b){
    rep[Find(a)] = Find(b);
}

int ile_uz = 0;

ll n, m;
void policz_mst(){
    vis[1] = true;

    while(sz(nieobecne)){
        int akt = -1;
        
        if(sz(do_odw)){
            akt = do_odw.back();
            do_odw.pop_back();
        }
        else{
            while(vis[(*kandydaci.begin()).s.s])
                kandydaci.erase(kandydaci.begin());
            akt = (*kandydaci.begin()).s.s;
            assert(nieobecne.count(akt));

            vis[akt] = true;
            mst += (*kandydaci.begin()).f;
            
            pair<int, int> kraw = (*kandydaci.begin()).s;
            MST[kraw.f].pb(kraw.s);
            MST[kraw.s].pb(kraw.f);
            MST_kraw.pb(kraw);
            nieobecne.erase(akt);
            kandydaci.erase(kandydaci.begin());
        }

        vector<int> do_wywalenia;
        for(auto & u : nieobecne){
            if(G[akt].count(u)){
                kandydaci.insert({G[akt][u], {akt, u}});
            }
            else{
                do_wywalenia.pb(u);
                do_odw.pb(u);

                vis[u] = 1;
                
                MST[akt].pb(u);
                MST[u].pb(akt);
                MST_kraw.pb({u, akt});
                ile_uz++;
            }
        }
        for(auto & u : do_wywalenia)
            nieobecne.erase(u);
    }
}

int it = 0;
void dfs(int start, int pre, vi & odw){
    odw.pb(start);
    it++;
    if(it > n * 2)
        return;
    for(auto & u : MST[start])
        if(u != pre)
            dfs(u, start, odw);
}

void solve(){
    cin >> n >> m;

    for(int i = 2; i <= n; i++)
        nieobecne.insert(i);

    int XOR = 0;

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;

        G[a][b] = c;
        G[b][a] = c;

        XOR ^= c;
    }
    policz_mst();

    for(int i = 1; i <= n; i++)
        rep[i] = i;

    // for(auto & u : MST_kraw){
        // assert(Find(u.f) != Find(u.s));
        // Union(u.f, u.s);
    // }

    ll wszystkie = 1ll * n * (n - 1) / 2;

    if(wszystkie - m == ile_uz){
        for(auto & u : MST_kraw){
            if(G[u.f].count(u.s))
                continue;

            vector<int> A, B;
            it = 0;
            dfs(u.f, u.s, A);
            dfs(u.s, u.f, B);

            for(auto & a : A)
                for(auto & b : B)
                    if(a != u.f or b != u.s)
                        XOR = min(XOR, G[a][b]);
        }

        mst += XOR;
    }

    cout << mst << '\n';
}

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

    int t = 1;
    // cin >> t;

    while(t--){
        solve();
    }
}