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 M=998244353;
const long long inf=101010101010101ll;
const int N=1000005;
int n,i,j,k,f[N],m;
int g[1005][1005],cnt[N],siz[N];
struct str{
	int u,v,w;
}e[N];
vector<int> t[N],p;
bool cmp(str a,str b)
{
	return a.w<b.w;
}
int Find(int x)
{
	return f[x]?f[x]=Find(f[x]):x;
}
void uniot(int x,int y)
{
	int u=Find(x),v=Find(y);
	if(u!=v)
	{
		f[u]=v;
		siz[v]+=siz[u];
	}
}
long long ans;
void cal3(int u,int v,int w)
{
	int i,j,x;
	long long s=0;
	for(i=1;i<=m;++i)
		if(w<e[i].w)
			break;
	x=i;
	for(i=m+1;i>x;--i)
		e[i]=e[i-1];
	e[i]={u,v,w};
	for(i=1;i<=n;++i)
		f[i]=0;
	for(i=1;i<=n;++i)
		for(j=i+1;j<=n;++j)
			if(!g[i][j]&&(i!=u||j!=v))
				uniot(i,j);
	for(i=1;i<=m+1;++i)
	{
		int x=Find(e[i].u),y=Find(e[i].v);
		if(x!=y)
		{
			f[x]=y;
			s+=e[i].w;
		}
	}
	for(i=x;i<=m;++i)
		e[i]=e[i+1];
	ans=min(ans,s);
}
void cal()
{
	int mn=0;
	for(i=1;i<=m;++i)
		mn^=e[i].w;
	ans=1111111111111111ll;
	sort(e+1,e+1+m,cmp);
	for(i=1;i<=n;++i)
		for(j=i+1;j<=n;++j)
			if(g[i][j]==0)
				cal3(i,j,mn);
	cout<<ans;
}
void cal2()
{
	memset(f,0,sizeof(f));
	for(i=1;i<=n;++i)
		siz[i]=1;
	for(i=1;i<=m;++i)
		t[max(e[i].u,e[i].v)].push_back(min(e[i].u,e[i].v));
	for(i=1;i<=n;++i)
	{
		for(auto it:t[i])
			++cnt[Find(it)];
		for(auto it:p)
			if(Find(it)==it)
				if(cnt[it]!=siz[it])
					uniot(i,it);
		if(Find(i)==i)
			p.push_back(i);
		for(auto it:p)
			cnt[it]=0;
	}
	sort(e+1,e+1+m,cmp);
	for(i=1;i<=m;++i)
		if(Find(e[i].u)!=Find(e[i].v))
		{
			uniot(e[i].u,e[i].v);
			ans+=e[i].w;
		}
	cout<<ans;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i)
		scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
	if(m>=1ll*n*(n-1)/2-n)
	{
		for(i=1;i<=m;++i)
			g[e[i].u][e[i].v]=g[e[i].v][e[i].u]=1;
		bool flag=true;
		for(i=1;i<=n;++i)
			for(j=i+1;j<=n;++j)
				if(!g[i][j])
				{
					int x=Find(i),y=Find(j);
					if(x==y)
						flag=false;
					else
						uniot(x,y);
				}
		if(!flag)
			cal2();
		else
			cal();
	}
	else
		cal2();
}
