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>
#define re register
#define int long long
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
struct edge{int to,next;}e[2000002];
struct node{
	int x,y,z;
	bool operator <(const node a)const{return z<a.z;}
}p[1000002];
int t,n,m,a[1000002],cnt,dep[1000002],head[1000002],RT[1000002],b[1000002],sum,sz[1000002],fa[1000002],tp,v[1000002],top[1000002],son[1000002],siz[1000002],d[1000002];
long long ans;
map<int,int>vv;
set<int>S;
inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
inline void dfs(re int x,re int y){
	dep[x]=dep[y]+1,fa[x]=y,siz[x]=1,d[x]+=(sz[RT[x]]>1);
	for(re int i=head[x];i;i=e[i].next)
		if(e[i].to^y){
			d[e[i].to]=d[x],dfs(e[i].to,x),siz[x]+=siz[e[i].to];
			if(siz[e[i].to]>siz[son[x]])son[x]=e[i].to;
		}
}
inline void dfs1(re int x,re int y){
	if(son[x])dfs1(son[x],y);
	for(re int i=head[x];i;i=e[i].next)
		if(e[i].to^fa[x]&&e[i].to^son[x])
			dfs1(e[i].to,e[i].to);
}
inline int lca(re int x,re int y){
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]])y=fa[top[y]];
		else x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
set<int>::iterator it,stk[1000002];
inline void add(re int x,re int y){printf("aaa%d %d\n",x,y);e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline void merge(re int x,re int y){
	fa[x]=y;
}
signed main(){
	n=read(),m=read();
	for(re int i=1,x,y,z;i<=m;++i){
		x=p[i].x=read(),y=p[i].y=read(),z=p[i].z=read();
		sum^=z;
		if(x>y)swap(x,y);
		add(y,x);
	}
	for(re int i=1;i<=n;++i){
		vv.clear(),fa[i]=i;
		for(re int j=head[i];j;j=e[j].next)++vv[root(e[j].to)];
		sz[i]=1,b[i]=i,tp=0;
		for(it=S.begin();it!=S.end();++it)if(vv[*it]!=sz[*it])stk[++tp]=it,sz[i]+=sz[*it],merge(*it,i);
		for(re int j=1;j<=tp;++j)S.erase(stk[j]);S.insert(i);
	}
	for(re int i=1;i<=m;++i)p[i].x=root(p[i].x),p[i].y=root(p[i].y);
	sort(p+1,p+m+1);
	int ttt=0;
	for(re int i=1;i<=n;++i)if(root(i)==i)++ttt;
	for(re int i=1;i<=n;++i)RT[i]=root(i);
	for(re int i=1;i<=n;++i)fa[i]=i,head[i]=0;cnt=0;
	for(re int i=1;i<=m;++i){
		if(root(p[i].x)^root(p[i].y)){
			fa[root(p[i].x)]=root(p[i].y),ans+=p[i].z;
			add(p[i].x,p[i].y),add(p[i].y,p[i].x);
		}
		else v[i]=1;
	}
	if(1ll*n*(n-1)/2-m>n-ttt)printf("%lld",ans);
	else{
		dfs(1,0),dfs1(1,1);
		for(re int i=1;i<=m;++i){
			if(!v[i]){
				re int x=lca(p[i].x,p[i].y);
				if(d[p[i].x]+d[p[i].y]-d[lca(p[i].x,p[i].y)]-d[fa[lca(p[i].x,p[i].y)]])sum=min(sum,p[i].z);
			}
		}
		printf("%lld",ans+sum);
	}
}
