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 Re register int
typedef long long ll;

const int N = 200005, M = 900;
struct edg
{
	int l, r, s;
}eg[N], a[M];
int n, m, s, t, cnt, fa[M], d[N], g[N], hea[N], nxt[N << 1], to[N << 1];
bool b[M][M];
ll ans;

inline int read()
{
	char c = getchar();
	int ans = 0;
	while (c < 48 || c > 57) c = getchar();
	while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
	return ans;
}

inline bool cmp(edg x, edg y)
{
	return x.s < y.s;
}

inline void add(int x, int y)
{
	nxt[++cnt] = hea[x], to[cnt] = y, hea[x] = cnt;
}

inline int find_fa(int x)
{
	return (fa[x] ^ x) ? fa[x] = find_fa(fa[x]) : x;
}

inline void del(int x)
{
	for (Re i = hea[x]; i; i = nxt[i]) g[to[i]] = x;
	for (Re i = 1; i <= n; ++i)
		if (g[i] ^ x && d[i] > 1)
		{
			--d[i];
			if (d[i] == 1) del(i);
			return;
		}
}

int main()
{
	n = read(), m = read();
	for (Re i = 1; i <= m; ++i) eg[i].l = read(), eg[i].r = read(), eg[i].s = read(), s ^= eg[i].s;
	sort(eg + 1, eg + m + 1, cmp);
	if (1ll * n * (n - 1) / 2 < 1ll * n + m)
	{
		ans = 1e14;
		for (Re i = 1; i <= m; ++i) b[eg[i].l][eg[i].r] = 1;
		for (Re i = 1; i < n; ++i)
			for (Re j = i + 1; j <= n; ++j)
				if (!b[i][j] && !b[j][i]) a[++t].l = i, a[t].r = j;
		int mm = 0;
		for (Re i = 1; i <= n; ++i) fa[i] = i;
		for (Re i = 1, j = n - 1; i <= m; ++i)
		{
			int u = eg[i].l, v = eg[i].r;
			if (find_fa(u) ^ find_fa(v))
			{
				eg[++mm] = eg[i], fa[fa[u]] = fa[v], --j;
				if (!j) break;
			}
		}
		m = mm;
		for (Re i = 1; i <= t; ++i)
		{
			for (Re j = 1; j <= n; ++j) fa[j] = j;
			int w = n - 1;
			ll tot = 0;
			for (Re j = 1; j < i; ++j)
			{
				int u = a[j].l, v = a[j].r;
				if (find_fa(u) ^ find_fa(v))
				{
					fa[fa[u]] = fa[v], --w;
					if (!w)
					{
						putchar(48);
						return 0;
					}
				}
			}
			for (Re j = i + 1; j <= t; ++j)
			{
				int u = a[j].l, v = a[j].r;
				if (find_fa(u) ^ find_fa(v))
				{
					fa[fa[u]] = fa[v], --w;
					if (!w)
					{
						putchar(48);
						return 0;
					}
				}
			}
			for (Re j = 1; j <= m; ++j)
			{
				if (eg[j - 1].s <= s && eg[j].s > s && find_fa(a[i].l) ^ find_fa(a[i].r)) fa[fa[a[i].l]] = fa[a[i].r], --w, tot += s;
				int u = eg[j].l, v = eg[j].r;
				if (find_fa(u) ^ find_fa(v))
				{
					fa[fa[u]] = fa[v], --w, tot += eg[j].s;
					if (!w || tot >= ans) break;
				}
			}
			if (w) tot += s;
			if (tot < ans) ans = tot;
		}
	}
	else
	{
		d[1] = (n << 1) + m;
		for (Re i = 2; i <= n; ++i) d[i] = n - 1;
		for (Re i = m; i; --i)
		{
			int u = eg[i].l, v = eg[i].r;
			if (d[u] > 1 && d[v] > 1)
			{
				--d[u], --d[v], add(u, v), add(v, u);
				if (d[u] == 1) del(u);
				if (d[v] == 1) del(v);
			}
			else ans += eg[i].s;
		}
	}
	printf("%lld", ans);
	return 0;
}
