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=214514;
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define int long long
struct ask{int x,y,z;}q[N];
int n,m,sp,ss,st,as,sm,mm,ct,v[N],f[N],gg[N],al[N],c[N];
set<int>s,G[N];
set<int>::iterator it;
bool cmp(ask a,ask b){return a.z<b.z;}
int get(int x){return gg[x]==x?x:gg[x]=get(gg[x]);} 
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void bfs(int x){
    queue<int>q;s.erase(x);
    q.push(x);f[x]=ss;
    while(!q.empty()){
        int k=q.front();q.pop();
        for(it = s.begin();it != s.end();){
            int to = *it++;
            if(!G[to].count(k)){s.erase(to);q.push(to);f[to]=ss;}
        }
    }
}//求补图连通块
signed main(){scanf("%lld%lld",&n,&m);
    rep(i,1,n)s.insert(i),gg[i]=i;
    rep(i,1,m){scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].z)
        ,mm^=q[i].z,G[q[i].x].insert(q[i].y),G[q[i].y].insert(q[i].x);
    }rep(i,1,n)if(!f[i])ct++,ss=i,bfs(i);
    rep(i,1,n)c[f[i]]++;
    rep(i,1,m)if(f[q[i].x]==f[q[i].y])al[f[q[i].y]]++;
    rep(i,1,n)if(c[f[i]]<=(1ll*(c[f[i]]*(c[f[i]]-1)/2)-al[f[i]]))sp=1;//判补图环
    sort(q+1,q+m+1,cmp);st=2e9;
    rep(i,1,m){int x=find(q[i].x),y=find(q[i].y);
        if(x==y){v[i]=1;continue;}
        f[x]=y;as+=q[i].z;
    }
    rep(i,1,m)if(!v[i])gg[get(q[i].x)]=get(q[i].y);//将树边缩起来
    rep(i,1,m)if(v[i]&&get(q[i].x)!=get(q[i].y))st=min(st,q[i].z);//如果f不相同,那么说明他可以替换边
    if(!sp)as+=min(st,mm);printf("%lld\n",as);
} 