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;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';c=getchar();
	}
	return x*f;
}
#define N 400005
const int inf=1e9;
struct seg{
	int l,r,pos;
	long long maxn,laz;
}t[N<<3];
#define IT multiset<int>::iterator
multiset<int> b,di[N];
inline void push(int p){
	if(t[p].laz!=0){
		t[p<<1].maxn+=t[p].laz;t[p<<1].laz+=t[p].laz;
		t[p<<1|1].maxn+=t[p].laz;t[p<<1|1].laz+=t[p].laz;
		t[p].laz=0;
	}
}
inline void up(int p){
	t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
	if(t[p<<1].maxn==t[p].maxn)t[p].pos=t[p<<1].pos;
	if(t[p<<1|1].maxn==t[p].maxn)t[p].pos=t[p<<1|1].pos;
}

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].maxn=0,t[p].pos=0;t[p].laz=0;
	if(l==r){
		t[p].pos=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	up(p);
}
void change(int p,int l,int r,long long ad){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].maxn+=ad;
		t[p].laz+=ad;
		return ;
	}
	int mid=(t[p].l+t[p].r)>>1;
	push(p);
	if(l<=mid)change(p<<1,l,r,ad);
	if(r>mid)change(p<<1|1,l,r,ad);
	up(p);
}
struct Bian{
	int u,v,w,in;
}bian[N];
priority_queue<pair<int , int> > q;
int tot=1,head[N],ver[N<<1],nex[N<<1],edge[N<<1];
inline void add(int x,int y,int z){
	nex[++tot]=head[x];head[x]=tot;ver[tot]=y;edge[tot]=z;
//	cout<<x<<" "<<y<<":"<<z<<endl;
}
vector<int> sub,to[N],ed[N];
int in[N],cnt,n,m;

long long ans;
inline void ad(int x){
	change(1,1,n,1);
	for(int i=0;i<(int)to[x].size();++i){
		int y=to[x][i];
		change(1,y,y,-1);
		q.push(make_pair(-bian[ed[x][i]].w,ed[x][i]));
	}
	change(1,x,x,-inf);
	in[x]=1;
	sub.push_back(x);
}
int f[N][20],T=19,dep[N];
vector<int> ad_[N],del_[N];
void dfs1(int x,int las){
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==las)continue;
		dep[y]=dep[x]+1;
		f[y][0]=x;
		for(int j=1;j<=T;++j)f[y][j]=f[f[y][j-1]][j-1];
		dfs1(y,x);
	}
}
inline int get_lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int j=T;j+1;--j)if(dep[f[y][j]]>=dep[x])y=f[y][j];
	if(x==y)return x;
	for(int j=T;j+1;--j)if(f[y][j]!=f[x][j])x=f[x][j],y=f[y][j];
	return f[x][0];
}
inline int fin(int x,int td){
	for(int j=T;j+1;--j)if(dep[f[x][j]]>=td)x=f[x][j];
	return x;
}
int minn=inf;
void dfs2(int x,int las){
	
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==las)continue;
		dfs2(y,x);
		if(edge[i]==0){
			if(!di[y].empty()){
				minn=min(minn,*di[y].begin());
			}
		}
		for(int j=0;j<(int)del_[y].size();++j){
			int w=del_[y][j];
//			cout<<y<<":"<<w<<endl;
			if(di[y].find(w)!=di[y].end()){
				di[y].erase(di[y].find(w));
			}
		}
		if(di[y].size()>di[x].size())swap(di[y],di[x]);
		for(IT it=di[y].begin();it!=di[y].end();++it){
			di[x].insert(*it);
		}
		
	}
//	cout<<":"<<x<<endl;
	for(int j=0;j<(int)ad_[x].size();++j){
		int w=ad_[x][j];
		di[x].insert(w);
	}
//	cout<<(*di[x].begin())<<endl;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("C.out","w",stdout);
	n=read(),m=read();int nw=0;
	for(int i=1;i<=m;++i){
		bian[i].u=read(),bian[i].v=read(),bian[i].w=read();bian[i].in=0;
	//	q.push(make_pair(-bian[i].w,i));
		nw^=bian[i].w;
		to[bian[i].u].push_back(bian[i].v);ed[bian[i].u].push_back(i);
		to[bian[i].v].push_back(bian[i].u);ed[bian[i].v].push_back(i);
	}
	build(1,1,n);
	ad(1);
	for(int T=2;T<=n;++T){
		int maxn=t[1].maxn,pos=t[1].pos,y;
		if(maxn>0){
			b.clear();
			for(int i=0;i<(int)to[pos].size();++i){
				b.insert(to[pos][i]);
			}
			for(int i=0;i<(int)sub.size();++i){
				y=sub[i];
				if(b.find(y)==b.end())break;
			}
			add(y,pos,0);add(pos,y,0);
			ad(pos);++cnt;
			continue;
		}
		while(!q.empty()){
			int id=q.top().second,u=bian[id].u,v=bian[id].v;
			if((in[u]&in[v])==0)break;
			q.pop();
		}
		int id=q.top().second,u=bian[id].u,v=bian[id].v;
		ans+=bian[id].w;bian[id].in=1;
		add(u,v,bian[id].w);add(v,u,bian[id].w);
		if(in[v])swap(u,v);
		ad(v);
	}
	if(1ll*n*(n-1)/2!=cnt+m){
		printf("%lld\n",ans);
		return 0;
	}
	dep[1]=1;
	dfs1(1,0);
	for(int i=1;i<=m;++i){
		if(!bian[i].in){
			int x=bian[i].u,y=bian[i].v,w=bian[i].w,lca=get_lca(x,y);
//			if(x==4&&y==1)cout<<fin(4,dep[1]+1)<<endl;
			if(x!=lca){
				ad_[x].push_back(w);
				del_[fin(x,dep[lca]+1)].push_back(w);
			}
			if(y!=lca){
				ad_[y].push_back(w);
				del_[fin(y,dep[lca]+1)].push_back(w);
			}
		}
	}
	b.clear();
	dfs2(1,0);
//	cout<<ans<<" "<<nw<<" "<<minn<<endl;
	ans=ans+min(nw,minn);
	printf("%lld\n",ans);
	return 0;
}
/*
5 9
5 1 62
1 3 27
5 2 55
2 1 96
4 5 51
3 4 30
4 1 45
2 4 81
3 2 76

*/
	
