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 rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define inf 1000000010
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
	x=0;int f=0;char s=gc();
	while(!isdigit(s))f|=s=='-',s=gc();
	while(isdigit(s))x=x*10+s-48,s=gc();
	x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
	if(x<0)pc('-'),x=-x;
	do{buf[++cc]=int(x%10);x/=10;}while(x);
	while(cc)pc(buf[cc--]+'0');pc(' ');
}
const int N=2e5+10;
namespace LCA{
	vector<pii>e[N];
	int fa[N][21],dep[N],s[N];
	void init(){dep[1]=1;}
	void add(int x,int y,int w){
		e[x].push_back(mp(y,w));
		e[y].push_back(mp(x,w));
	}
	void dfs(int x){
		rep(i,1,18)fa[x][i]=fa[fa[x][i-1]][i-1];
		for(pii i:e[x]){
			int y=i.fi,w=i.se;
			if(y==fa[x][0])continue;
			fa[y][0]=x;dep[y]=dep[x]+1;
			s[y]=s[x];if(!w)s[y]++;
			dfs(y);
		}
	}
	int getlca(int x,int y){
		if(dep[x]<dep[y])swap(x,y);
		dwn(i,18,0)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
		if(x==y)return x;
		dwn(i,18,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	int calc(int x,int y){return s[x]+s[y]-2*s[getlca(x,y)];}
	bool check(int x,int y){return fa[x][0]==y||fa[y][0]==x;}
}
int n,m,t,fa[N],siz[N],sum[N],pre[N];
vector<int>e[N];
int tp,sta[N],dd,del[N];
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
set<int>s;
set<int>::iterator it;
struct edge{int x,y,z;}a[N];
bool cmp(edge p1,edge p2){return p1.z<p2.z;}
int main(){
	int cc=0;
	qr(n),qr(m);
	rep(i,1,n){
		fa[i]=i;siz[i]=1;
	}
	rep(i,1,m){
		int x,y,z;qr(x),qr(y),qr(z);
		cc^=z;a[i]=(edge){x,y,z};
		if(x>y)swap(x,y);
		e[y].push_back(x);
	}
	sort(a+1,a+m+1,cmp);
	s.insert(1);
	int done=0;
	LCA::init();
	rep(i,2,n){
		for(int y:e[i]){
			sum[findfa(y)]++;
			sta[++tp]=findfa(y);
		}
		for(it=s.begin();it!=s.end();it++){
			int now=(*it);
			if(sum[now]!=siz[now]){
				fa[now]=i;siz[i]+=siz[now];
				done++;del[++dd]=now;
				LCA::add(i,now,0);
			}
		}
		while(dd)s.erase(del[dd--]);
		s.insert(i);
		while(tp)sum[sta[tp--]]=0;
	}
	ll val=0;
	rep(i,1,m){
		int x=a[i].x,y=a[i].y;
		if(findfa(x)!=findfa(y)){
			fa[findfa(x)]=findfa(y),val+=(ll)a[i].z;
			LCA::add(x,y,a[i].z);
		}
	}
	if(cc!=0&&(ll)(done+m)==1ll*n*(n-1)/2){
		ll ans=val+(ll)cc;
		LCA::dfs(1);
		rep(i,1,m)if(!LCA::check(a[i].x,a[i].y)&&LCA::calc(a[i].x,a[i].y)>0){
			ans=min(ans,val+(ll)a[i].z);
			break;
		}
		cout<<ans<<endl;
	}
	else cout<<val<<endl;
	return 0;
}
