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;
const int N = 2e5 + 5;
#define int long long
int n,m,tot;
struct Edge {
	int u,v,w;
	inline bool operator < (const Edge &o) {
		return w < o.w;
	}
} e[N],e2[N];
vector<int> G[N];
int pre[N],nxt[N],vis[N];
set<int> s[N];
int f[N],siz[N],cnt[N];
int getf(int u) {
	return f[u] == u ? u : f[u] = getf(f[u]);
}
inline void merge(int u,int v) {
	u = getf(u),v = getf(v);
	if(u != v) f[u] = v;
}
void dfs1(int u) {
	vis[u] = 1;
	nxt[pre[u]] = nxt[u];
	pre[nxt[u]] = pre[u];
	for(int i = nxt[0];i != n+1;i = nxt[i])
		if(*(s[u].find(i)) != i) {
			dfs1(i);
			merge(u,i);
			e2[++tot] = {u,i,0};
		}
}
int sav[N];
long long ans = 4e18;
void Kruskal() {
	for(int i = 1;i <= n;++i)
		sav[i] = f[i];
	long long res = 0;
	for(int i = 1;i <= m;++i) {
		int u = e[i].u,v = e[i].v;
		if(getf(u) != getf(v)) {
			res += e[i].w;
			f[getf(u)] = getf(v);
		}
	}
	for(int i = 1;i <= n;++i)
		f[i] = sav[i];
	ans = min(ans,res);
}
void dfs2(int u,int fa) {
	for(int i = 0;i < G[u].size();++i)
		if(G[u][i] != fa) {
			f[G[u][i]] = f[u];
			dfs2(G[u][i],u);
		}
}
int du[N];
int judge() {
	for(int i = 1;i <= n;++i) ++siz[getf(i)];
	for(int i = 1;i <= m;++i) if(getf(e[i].u) == getf(e[i].v))
		++cnt[e[i].u],++cnt[e[i].v];
	//cout<<siz[4]<<cnt[1]<<endl;
	for(int i = 1;i <= n;++i) if(cnt[i] != siz[getf(i)]-du[i]-1) {
		//cout<<cnt[i]<<i<<du[i]<<endl;
		Kruskal();
		cout << ans << endl;
		return 1;
	}
	return 0;
}
signed main() {
	cin >> n >> m;
	nxt[0] = 1;
	for(int i = 1;i <= n;++i)
		pre[i] = i-1,nxt[i] = i+1,f[i] = i;
	pre[n+1] = n;
	long long res = 0;
	for(int i = 1;i <= m;++i) {
		cin >> e[i].u >> e[i].v >> e[i].w;
		s[e[i].u].insert(e[i].v);
		s[e[i].v].insert(e[i].u);
		res ^= e[i].w;
	}
	sort(e+1,e+m+1);
	for(int i = 1;i <= n;++i) if(!vis[i]) dfs1(i);
	for(int i = 1;i <= tot;++i) {
		G[e2[i].u].push_back(e2[i].v);
		G[e2[i].v].push_back(e2[i].u);
		++du[e2[i].u];
		++du[e2[i].v];
	}
	if(judge()) return 0;
	//n <= sqrt(2e5)
	Kruskal();
	ans += res;
	for(int i = 1;i <= tot;++i) {
		f[e2[i].u] = e2[i].u;
		f[e2[i].v] = e2[i].v;
		dfs2(e2[i].u,e2[i].v);
		dfs2(e2[i].v,e2[i].u);
		Kruskal();
		f[e2[i].u] = e2[i].u;
		dfs2(e2[i].u,e2[i].u);
	}
	cout << ans << endl;
	return 0;
}
