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>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

struct edge{ lint u, v, w; };
vector<edge> edges;
vector<int> adj[200005];
bool tempbad[200005];
bool vis[200005];
vector<int> unvis;
lint n, m; 

void dfs(int u){
	vis[u] = true;
	
	//show(u);
	//for(int x : unvis) cout << x << " "; cout << "\n";
	
	int i = 0;
	vector<int> tovisit;
	while(i < sz(unvis)){
		int v = unvis[i];
		
		auto it = lower_bound(all(adj[u]), v);
		if(it != adj[u].end() and *it == v){
			i++;
			continue;
		}
		
		unvis[i] = unvis.back(); unvis.pop_back();
		
		if(u != v){
			//show2(u,v);
			edges.push_back({u,v,0});
			tovisit.push_back(v);
		}
	}
	
	for(int v : tovisit) dfs(v);
}

namespace ufds{
	int p[200005];
	int findSet(int u){
		if(p[u] == u) return u;
		else return p[u] = findSet(p[u]);
	}
	bool unionset(int u, int v){
		u = findSet(u), v = findSet(v);
		if(u == v) return false;
		if(u&v&rand()&1) swap(u, v);
		p[u] = v;
		return true;
	}
	void reset(){
		for(int i = 0;i <= n;i++) p[i] = i;
	}
};

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	lint xorsum = 0;
	
	cin >> n >> m;
	edges.resize(m);
	for(int i = 0;i < m;i++){
		int u, v, w; cin >> u >> v >> w;
		edges[i] = {u,v,w};
		adj[u].push_back(v);
		adj[v].push_back(u);
		xorsum ^= w;
	}
	
	for(int i = 1;i <= n;i++) unvis.push_back(i);
	for(int i = 1;i <= n;i++) sort(all(adj[i]));
	
	for(int i = 1;i <= n;i++){
		if(!vis[i]) dfs(i);
	}
	
	sort(all(edges), [&](edge &a, edge &b){ return a.w < b.w; });
	ufds::reset();
	
	vector<edge> nonzero, unused;
	lint ans = 0; lint zero = 0;
	for(edge e : edges){
		if(ufds::unionset(e.u, e.v)){
			ans += e.w;
			if(e.w == 0) zero++;
			else nonzero.push_back(e);
		}
		else if(e.w != 0) unused.push_back(e);
	}
	
	if(zero == n*(n-1)/2LL - m){
		ufds::reset();
		for(edge e : nonzero) ufds::unionset(e.u, e.v);
		for(edge e : unused){
			if(ufds::findSet(e.u) != ufds::findSet(e.v)) xorsum = min(xorsum, (lint) e.w);
		}
		ans += xorsum;
	}
	
	cout << ans;
}
