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 ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 300005;
const int mod = 998244353;
set<int>non;
set<int>g[maxn];
int d[maxn];
int d2[maxn];
int fi(int x) {
    return d[x] == x ? x : d[x] = fi(d[x]);
}
int fi2(int x) {
    return d2[x] == x ? x : d[x] = fi(d[x]);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<pair<int,pair<int,int>>>e;
    int xo = 0;
    ll fe = (1LL * n * (n - 1)) / 2 - m;
    int mi = 1e9;
    f(m){
        int add1,add2, add3;
        cin >> add1 >> add2 >> add3;
        xo ^= add3;
        g[add1].insert(add2);
        g[add2].insert(add1);
        e.pb({add3,{add1,add2}});
    }
    f1(n){
        non.insert(i);
    }
    int cnt = 0;
    int cc[n + 5] = {};
    while(non.size()){
        cnt++;
        vector<int>c;
        int nxt = *non.begin();
        non.erase(nxt);
        queue<int>q;
        q.push(nxt);
        while(!q.empty()){
            int now = q.front();
            cc[now] = cnt;
            c.pb(now);
            q.pop();
            set<int>era;
            for(auto i:non){
                if(!g[now].count(i)){
                    era.insert(i);
                }
            }
            for(auto i:era){
                q.push(i);
                non.erase(i);
            }
        }
    }
    sort(all(e));
    int need = n - 1;
    f1(cnt) {
        d[i] = i;
    }
    ll ans = 0;
    f1(n) {
        d2[i] = i;
    }
    for (auto &i : e) {
        int x = fi(cc[i.S.F]);
        int y = fi(cc[i.S.S]);
        if (x != y) {
            d[x] = y;
            ans += i.F;
            need--;
            int X = fi2(i.S.F);
            int Y = fi2(i.S.S);
            d2[X] = Y;
        }
        else if (fi2(i.S.F) != fi2(i.S.S)) {
            mi = min(mi, i.F);
        }
    }
    if (need == fe) {
        ans += min(mi, xo);
    }
    cout << ans << '\n';
}