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<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const long long INF=1e18;
int n,m,t,ct[200002],f[200002];
long long ybj[802][802],bj[802][802],d[200002];
bool fl[200002];
vector<int>g[200002];
typedef struct{
	int x,y,w;
}P;
bool cmp(P aa,P bb){
	return (aa.w<bb.w);
}
P p[200002],q[800002],h[800002];
int find(int x){
	if (f[x]==x)return x;
	return f[x]=find(f[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	if (n<=800)
	{
		for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		ybj[i][j]=INF;
	}
	for (int i=1;i<=m;i++)
	{
	    scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);t^=p[i].w;
		g[p[i].x].push_back(p[i].y);g[p[i].y].push_back(p[i].x);
		if (n<=800)
		{
			ybj[p[i].x][p[i].y]=ybj[p[i].y][p[i].x]=p[i].w;
		}
	}
	if ((long long)n*(n-1)/2-m>=n)
	{
		int Max=-1,maxx=-1;
		for (int i=1;i<=n;i++)
		{
			if (n-1-(int)g[i].size()>Max)
			{
				Max=n-1-(int)g[i].size();maxx=i;
			}
		}
		memset(fl,0,sizeof(fl));
		for (int i=1;i<=n;i++)f[i]=i;
		for (int i=0;i<g[maxx].size();i++)fl[g[maxx][i]]=1;
	    int cnt=0;
		for (int i=1;i<=n;i++)
		if (!fl[i]){f[find(i)]=find(maxx);cnt++;}
		for (int i=1;i<=n;i++)
		if (find(i)==find(maxx))
		{
			for (int j=0;j<g[i].size();j++)ct[g[i][j]]++;
		}
		for (int i=1;i<=n;i++)
		if (find(i)!=find(maxx))
		{
			memset(fl,0,sizeof(fl));
			for (int j=0;j<g[i].size();j++)fl[g[i][j]]=1;
			for (int j=1;j<=n;j++)if (!fl[j] && find(j)!=find(maxx))f[find(i)]=find(j);
		}
		for (int i=1;i<=n;i++)
		if (find(i)!=find(maxx) && ct[i]<cnt)f[find(i)]=find(maxx);
		sort(p+1,p+m+1,cmp);
		long long ans=0;
		for (int i=1;i<=m;i++)
		if (find(p[i].x)!=find(p[i].y))
		{
			f[find(p[i].x)]=find(p[i].y);
			ans+=p[i].w;
		}
		printf("%lld\n",ans);
	}
	else
	{
		int len=0;long long ans=INF;
		for (int i=1;i<=n;i++)
		{
			fl[i]=1;
			for (int j=0;j<g[i].size();j++)fl[g[i][j]]=1;
			for (int j=1;j<=n;j++)
			if (!fl[j] && i<j)
			{
				q[++len].x=i;q[len].y=j;q[len].w=0;
			}
			fl[i]=0;
			for (int j=0;j<g[i].size();j++)fl[g[i][j]]=0;
		}
		for (int i=1;i<=len;i++)
		{
			q[i].w=t;
			for (int j=1;j<=n;j++)
			for (int k=1;k<=n;k++)
			bj[j][k]=ybj[j][k];
			for (int j=1;j<=len;j++)
			{
				bj[q[j].x][q[j].y]=min(bj[q[j].x][q[j].y],(long long)q[j].w);
				bj[q[j].y][q[j].x]=min(bj[q[j].y][q[j].x],(long long)q[j].w);
			}
			for (int j=1;j<=n;j++)
			if (j==1)d[j]=0;else d[j]=bj[1][j];
			for (int j=1;j<=n;j++)fl[j]=0;
			fl[1]=1;
			long long sum=0;
			for (int j=2;j<=n;j++)
			{
				long long Min=INF;int minn=-1;
				for (int k=1;k<=n;k++)
				if (!fl[k])
				{
					if (d[k]<Min)
					{
						Min=d[k];minn=k;
					}
				}
				sum+=Min;fl[minn]=1;
				for (int k=1;k<=n;k++)
				if (!fl[k])d[k]=min(d[k],bj[minn][k]);
			}
			ans=min(ans,sum);
			q[i].w=0;
		}
		printf("%lld\n",ans);
	}
	return 0;
}