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 int long long
using namespace std;
 
int n,m,s;
struct nod {
 
	int u,v,w;	
	nod(){}
	nod(int a1,int a2,int a3){ u=a1,v=a2,w=a3;
	}
}g[2000005];
vector<nod> e[2000005]; 
 
int fa[2000005],vis[2000005];
int find(int x) {
	return fa[x]==x ? x:fa[x]=find(fa[x]);
}
 
bool cmp(nod i,nod j) {
	return i.w<j.w;
}

int fa2[2000005];
int find2(int x) {
	return fa2[x]==x ? x:fa2[x]=find2(fa2[x]);
}
 
signed main() {
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++) {
		cin>>u>>v>>w;
		g[i]=(nod){u,v,w};
		e[u].push_back((nod){u,v,w});
		e[v].push_back((nod){v,u,w});
		s^=w;
	}
	
	int flag=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	
	for(int i=1;i<=n;i++) {
		if(e[i].size()<n/2) {
			if(flag) {
				fa[find(i)]=find(flag);
			}
			else flag=i;
		} 
		else {
			for(int j=1;j<=n;j++) vis[j]=0;
			for(int j=0;j<e[i].size();j++) vis[e[i][j].v]++;
			for(int j=1;j<=n;j++) {
				if(vis[j] || j==i) continue;
				fa[find(i)]=find(j);
			}
		}
	} 
	
	
	for(int i=1;i<=n;i++) fa[i]=find(i);
	for(int i=1;i<=n;i++) fa2[i]=i;
 	sort(g+1,g+m+1,cmp);
 	int ans=0,cc=0,mi=1ll<<60;
 	
	for(int i=1;i<=m;i++) {
		int u=find(g[i].u),v=find(g[i].v); 
		int x=find2(g[i].u),y=find2(g[i].v);
		if(u!=v) {
			ans+=g[i].w,cc++;
			fa[u]=v;
			fa2[x]=y;			
		}
		else if(x != y) {
			mi=min(mi,g[i].w);
			fa2[x]=y;			
		}
	}
//	cout<<
	if(m+n-1-cc==n*(n-1)/2) cout<<ans+min(s,mi)<<'\n';
	else cout<<ans<<'\n';
}