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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
#define N 200002
struct node
{
	int x,y,len,id;
}b[N];
struct edge{int to,nxxt,len;}e[N<<1];
int n,m,head[N],cnt=1,XR,f[N],tb[N],tot;
bool vis[N];
set<int>s,ss;
queue<int>q;
set<int>::iterator it;
int getroot(int t){return !f[t]?t:f[t]=getroot(f[t]);}
inline void ins(int u,int v,int w){e[cnt]=(edge){v,head[u],w};head[u]=cnt++;}
bool cmp(node n1,node n2)
{
	return n1.len<n2.len;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		ins(x,y,z),ins(y,x,z);XR^=z;
		b[i]=(node){x,y,z,i};
	}
	for(int i=1;i<=n;i++)s.insert(i);
	for(int i=1;i<=n;i++)
	{
		q.push(i);
		while(!q.empty())
		{
			int a1=q.front();q.pop();tot=0;
			s.erase(a1);
		for(int j=head[a1];j;j=e[j].nxxt)
		{
			int t=e[j].to;tb[++tot]=t;
			vis[t]=1;
		}ss.clear();
		for(it=s.begin();it!=s.end();it++)
		{
			if(vis[*it])ss.insert(*it);
			else
			{
				int x=getroot(a1),y=getroot(*it);
				if(x^y)f[x]=y;
				q.push(*it);
			}
		}
		s=ss;
		for(int j=1;j<=tot;j++)vis[tb[j]]=0;
		}
	
	}ll ans=0;
	int mn=2e9,ct=0;
	memset(vis,0,sizeof(vis));
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=getroot(b[i].x),y=getroot(b[i].y);
		if(x^y)
		{ct++;
			f[x]=y;
			ans+=b[i].len;
			vis[b[i].id]=1;
		}
	}
	memset(f,0,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		int x=getroot(b[i].x),y=getroot(b[i].y);
		if(x^y)
		{
			f[x]=y;if(!vis[b[i].id])mn=min(mn,b[i].len);
		}
	}
	int rem=n-1-ct;
	if(1ll*n*(n-1)/2-m>rem)
	{
		printf("%lld\n",ans);return 0;
	}
	printf("%lld\n",ans+min(mn,XR));
}
/*
6 13
4 1 7
3 4 5
1 5 17
2 4 16
6 3 3
6 5 2
4 5 9
1 6 18
4 6 15
5 2 13
3 2 13
1 2 14
5 3 5
*/