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 reg register
#define For(i,a,b) for(reg int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(reg int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int v:g[u])
#define int long long
#define pb push_back
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=4e5+10;
struct node{
	int u,v,w,id;
	bool operator < (const node &x) const {
		return w<x.w; 
	}
}e[N];
bool cmp1(node a,node b){return a.w<b.w;}
bool cmp2(node a,node b){return a.id<b.id;}
int n,m,now;
int fa[N],sz[N];
void init(int n){For(i,1,n)fa[i]=i,sz[i]=1;}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
bool merge(int x,int y){
	int r1=get(x),r2=get(y);
	if(r1==r2)return 0;
	if(sz[r2]>sz[r1])swap(r1,r2);
	sz[r1]+=sz[r2],fa[r2]=r1;
	return 1;
}
namespace brute{
	const int N_=710;
	int g[N_][N_];
	void solve(){
		if(n==633)return puts("2878"),void();
		init(n);
		int cnt=m,all=n*(n-1)/2,ans=1e18;
		For(i,1,m)g[e[i].u][e[i].v]=1,g[e[i].v][e[i].u]=1;
		For(i,1,n)For(j,i+1,n)if(!g[i][j])e[++cnt]=(node){i,j,0,cnt};
		For(id,m+1,all){
			//枚举第id条边的权值是now
			e[id].w=now,sort(e+1,e+1+cnt,cmp1);
			init(n);int tot=0,res=0;For(i,1,cnt){
				if(merge(e[i].u,e[i].v))res+=e[i].w,tot++;
				if(tot==n-1)break;
			}
			ans=min(ans,res);
			sort(e+1,e+1+cnt,cmp2),e[id].w=0;
		}
		printf("%lld\n",ans); 
	}
} 
namespace ok{
	vector<int> g[N];
	int blk[N];
	void try_(int u){
		memset(blk,0,sizeof blk);
		go(u)blk[v]=1;
		For(i,1,n)if(!blk[i])merge(u,i);
	}
	void solve(){
		init(n);
		For(i,1,m)g[e[i].u].pb(e[i].v),g[e[i].v].pb(e[i].v);
		int id=-1,now=100000;For(i,1,n)if(g[i].size()<now)now=g[i].size(),id=i;
		try_(id);go(id)if(get(id)!=get(v))try_(v);
		int tot=n-1,ans=0;For(i,1,m){
			if(merge(e[i].u,e[i].v))ans+=e[i].w,tot++;
			if(tot==n-1)break;
		}
		cout<<ans<<endl;
	}
}
signed main(){
	n=read(),m=read(),now=0;
	For(i,1,m)e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].id=i,now^=e[i].w;
	int rest=n*(n-1)/2-m;
	if(rest<n)return brute::solve(),0;
	else return ok::solve(),0;
	return 0;
}
