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<algorithm>
#include<vector>
#include<set>
using namespace std;
int read() {
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int N=4e5+5;
struct HSHMAP {
	int head[131072],nxt[N],U[N],V[N],size;
	void add(int x,int y) {
		int u=1ll*x*y&131071;
		U[++size]=x;V[size]=y;
		nxt[size]=head[u];
		head[u]=size;
	}
	bool qry(int x,int y) {
		int u=1ll*x*y&131071;
		for(int i=head[u];i;i=nxt[i])if(U[i]==x&&V[i]==y)return 1;
		return 0;
	}
}F;
struct Edge {
	int u,v,w;
}e[N];
bool cmp(Edge p,Edge q) {
	return p.w<q.w;
}
int bel[N],n,m,fa[N],tot,E[N],flag,hh,cnt[N];
long long ans;
int find(int x) {
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
set<int>S;
void dfs(int u) {
	vector<int>bin;
	for(set<int>::iterator it=S.begin();it!=S.end();++it) {
		if(!F.qry(u,*it)) {
			bin.push_back(*it);
			bel[*it]=bel[u];
		}
	}
	for(int v:bin)S.erase(v);
	for(int v:bin)dfs(v);
}
int main() {
	n=read();m=read();
	for(int i=1,x,y;i<=m;++i) {
		x=read();y=read();e[i].w=read();
		F.add(x,y);
		F.add(y,x);
		e[i].u=x;e[i].v=y;
		hh^=e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;++i)fa[i]=i,S.insert(i);
	for(int i=1;i<=m;++i) {
		int u=find(e[i].u),v=find(e[i].v);
		if(u==v)e[i].w=-1;
		else fa[u]=v;
	}
	for(int i=1;i<=n;++i)
		if(!bel[i]) {
			bel[i]=++tot;
			S.erase(i); 
			dfs(i);
		}
	for(int i=1;i<=m;++i)
		if(bel[e[i].u]==bel[e[i].v])++E[bel[e[i].u]];
	for(int i=1;i<=n;++i)++cnt[bel[i]];
	for(int i=1;i<=tot;++i)
		if(1ll*cnt[i]*(cnt[i]-1)/2-E[i]>cnt[i]-1)flag=1;
	for(int i=1;i<=tot;++i)fa[i]=i;
	for(int i=1;i<=m;++i) {
		if(e[i].w==-1)continue;
		int u=find(bel[e[i].u]),v=find(bel[e[i].v]);
		if(u==v)hh=min(hh,e[i].w);
		else fa[u]=v,ans+=e[i].w;
	}
	if(flag)printf("%lld",ans);
	else printf("%lld",ans+1ll*hh);
	return 0;
}