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 <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;

class dsu
{
public:
	vector<int> p, s;
	dsu(int n) :p(vector<int>(n)), s(vector<int>(n, 1)) { clear(); }
	int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
	bool merge(int a, int b)
	{
		a = root(a), b = root(b);
		if (a == b) return false;
		if (s[a] < s[b]) swap(a, b);
		s[a] += s[b], p[b] = a;
		return true;
	}
	void clear() { for (int i = 0; i < p.size(); i++) p[i] = i; }
};
struct edge { int u, v, x; };
bool cmp(const edge& a, const edge& b) { return a.x < b.x; }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<edge> e(m);
	int x = 0;
	for (int i = 0; i < m; i++)
	{
		cin >> e[i].u >> e[i].v >> e[i].x;
		e[i].u--, e[i].v--;
		x ^= e[i].x;
	}
	sort(e.begin(), e.end(), cmp);
	ll edges0 = n * 1ll * (n - 1) / 2 - (ll)m;
	dsu d(n);
	set<int> nv;
	for (int i = 0; i < n; i++) nv.insert(i);
	vector<set<int> > g(n);
	for (edge& i : e) g[i.u].insert(i.v), g[i.v].insert(i.u);
	for (int i = 0; i < n; i++)
	{
		if (!nv.count(i)) continue;
		queue<int> q; q.push(i);
		nv.erase(i);
		while (!q.empty())
		{
			int u = q.front(); q.pop();
			set<int> nv2;
			for (int v : nv)
			{
				if (!g[u].count(v))
				{
					d.p[v] = i;
					q.push(v);
					edges0--;
				}
				else nv2.insert(v);
			}
			nv = nv2;
		}
	}
	vector<bool> need(m, false);
	ll sum = 0;
	for (int i = 0; i < m; i++)
	{
		if (d.merge(e[i].u, e[i].v))
		{
			need[i] = true;
			sum += e[i].x;
		}
	}
	if (!edges0)
	{
		ll plus = x; 
		d.clear();
		for (int i = 0; i < m; i++)
		{
			if (d.root(e[i].u) == d.root(e[i].v)) continue;
			d.merge(e[i].u, e[i].v);
			if (!need[i])
			{
				plus = min(plus, (ll)e[i].x);
				break;
			}
		}
		sum += plus;
	}
	cout << sum << "\n";
	return 0;
}