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 rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> Pair;
#define ll long long

const int maxn = 2e5 + 10;
const int N = maxn;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, m;
struct E {
	int u, v; ll w;
	bool operator<(const E& b)const {
		return w < b.w;
	}
};
vector<int>G[N];
vector<E>es, tes, tmp, mst;
int par[N];
void init(int n) { for (int i = 1; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unit(int x, int y) { par[find(x)] = find(y); }
bool same(int x, int y) { return find(x) == find(y); }
set<int>st;
void dfs(int u) {
	st.erase(u);
	for (int i = 0; i < (int)G[u].size() - 1; i++) {
		int x = G[u][i], y = G[u][i + 1], v;
		while (!st.empty() && st.upper_bound(x) != st.end() && (v = (*st.upper_bound(x))) < y) {
			tes.push_back({ u, v, 0 });
			dfs(v);
		}
	}
}
ll sum;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		G[u].push_back(v);
		G[v].push_back(u);
		es.push_back({ u, v, w });
		sum ^= w;
	}
	for (int i = 1; i <= n; i++) {
		G[i].push_back(0);
		G[i].push_back(n + 1);
		sort(G[i].begin(), G[i].end());
	}
	for (int i = 1; i <= n; i++)st.insert(i);
	while (!st.empty())dfs(*st.begin());
	sort(es.begin(), es.end());
	ll ans = 0;
	if ((1ll * n*(n - 1) / 2 - m) >= n) {
		init(n);
		for (E& e : tes) {
			int u = e.u, v = e.v;
			if (!same(u, v))unit(u, v);
		}
		for (E& e : es) {
			int u = e.u, v = e.v;
			if (!same(u, v)) {
				unit(u, v);
				ans += e.w;
			}
		}
		printf("%lld\n", ans);
	}
	else {
		init(n);
		for (E& e : es) {
			if (!same(e.u, e.v)) {
				mst.push_back(e);
				unit(e.u, e.v);
			}
		}
		ll ans = inf;
		for (E& e : tes) {
			tmp.clear();
			e.w = sum;
			tmp.insert(tmp.end(), tes.begin(), tes.end());
			tmp.insert(tmp.end(), mst.begin(), mst.end());
			sort(tmp.begin(), tmp.end());
			ll res = 0;
			init(n);
			for (E& p : tmp) {
				if (!same(p.u, p.v)) {
					unit(p.u, p.v);
					res += p.w;
				}
			}
			ans = min(ans, res);
			e.w = 0;
		}
		printf("%lld\n", ans);
	}
	return 0;
}