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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
vector<pair<lld,pair<lld,lld> > > edges;
vector<pair<lld,lld>> nei[1000000];
int deg[1000000];
bool visited[1000000];
int correspond[1000000];
class DSU{
	int sz[1000000];
	int par[1000000];
	public:
	void init(int N){
		rep(i,0,N){
			sz[i]=1;
			par[i]=i;
		}
	}
	int root(int node){
		if(par[node]==node)return node;
		par[node]=root(par[node]);
		return par[node];
	}
	bool unit(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return false;
		if(sz[a]<sz[b])swap(a,b);
		par[b]=a;
		sz[a]+=sz[b];
		return true;
	}
	bool same(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return true;
		return false;
	}
};
int main(){
	lld n,m;
	cin>>n>>m;
	lld tot=0;
	rep(i,0,m){
		lld x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		edges.push_back({z,{x,y}});
		tot^=z;
	}
	sort(edges.begin(),edges.end());
	lld comb=n*(n-1);
	comb/=2;
	comb-=m;
	rep(i,0,m){
		if(edges[i].second.first>edges[i].second.second)swap(edges[i].second.first,edges[i].second.second);	
	}
	if(comb<1000000 || n<=1000){
		set<pair<int,int> >s;
		rep(i,0,n){
			rep(j,i+1,n){
				s.insert({i,j});
			}
		}
		rep(i,0,m){
			s.erase({edges[i].second.first,edges[i].second.second});
		}
		DSU D;
		D.init(n);
		bool cycle=false;
		trav(a,s){
			//cout<<a.first<<" "<<a.second<<endl;
			if(!D.unit(a.first,a.second)){
				cycle=true;
			}
		}
		if(cycle){
			lld ans=0;
			trav(a,edges){
				if(D.unit(a.second.first,a.second.second))ans+=a.first;
			}
			cout<<ans<<endl;
		}
		else{
			lld ans=0;
			lld Mx=tot;
			//cout<<tot<<endl;
			trav(a,edges){
				if(D.same(a.second.first,a.second.second))Mx=min(Mx,a.first);
			}
			trav(a,edges){
				if(D.unit(a.second.first,a.second.second)){
					ans+=a.first;
				}			
			}
			cout<<ans+Mx<<endl;

		}
	}else{
		DSU D;
		D.init(n);
		trav(a,edges){
			nei[a.second.first].push_back({a.second.second,a.first});
			nei[a.second.second].push_back({a.second.first,a.first});
		}
		int chosen=0;
		rep(i,0,n){
			visited[i]=false;
			if(nei[i].size()<500){
				chosen=i;	
			}
		}
		D.init(n);
		trav(a,nei[chosen]){
			visited[a.first]=true;
		}
		visited[chosen]=true;
		int counter=0;
		rep(i,0,n){
			if(!visited[i])D.unit(chosen,i);
			else{
				correspond[i]=counter;
				counter++;
			}
		}
		rep(i,0,n){
			if(!visited[i]){
				correspond[i]=counter;
			}
		}
		counter++;
		D.init(counter);
		rep(i,0,n){
			if(visited[i]){
				int counter2=0;
				trav(a,nei[i]){
					if(!visited[a.first]){
						counter2++;	
					}
				}
				if(counter+counter2!=n+1){
					D.unit(counter-1,correspond[i]);
				}
			}
		}
		
		rep(i,0,m){
			edges[i].second.first=correspond[edges[i].second.first];
			edges[i].second.second=correspond[edges[i].second.second];
			if(edges[i].second.first>edges[i].second.second)swap(edges[i].second.first,edges[i].second.second);
			//cout<<edges[i].second.first<<" "<<edges[i].second.second<<endl;	
		}
		set<pair<int,int> >s;
		
		rep(i,0,counter){
			rep(j,i+1,counter){
				s.insert({i,j});
			}
		}
		rep(i,0,m){
			s.erase({edges[i].second.first,edges[i].second.second});
		}
		trav(a,s){
			D.unit(a.first,a.second);
		}
		
		lld ans=0;
		rep(i,0,m){
			if(D.unit(edges[i].second.first,edges[i].second.second)){
				ans+=edges[i].first;	
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
