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=200010;
#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);
	if(!sp)
	    as+=min(st,mm);
	printf("%lld\n",as);
} 