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 <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define MOD 1000000007LL
#define INFD INT_MAX
#define INFL 1000000000000000000LL
#define eps 1e-9
#define PI 3.14159265358979
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pow __pow
#define gcd __gcd
#define count __count
#define sd(x) scanf("%d", &(x))
#define slld(x) scanf("%lld", &(x))
#define pd(x) printf("%d\n", (x))
#define plld(x) printf("%lld\n", (x))
#define gc getchar
#define pll pair<ll, ll> 
#define contains(S, x) (S.find(x) != S.end())
#define loop(it, st, en) for(ll it = (st); it <= (en); it++)

const ll N = 2e5;
const ll M = 2e5;

vector<ll> adj[N + 1];
vector<pair<ll, pll> > edges;
ll rootPrime[N + 1];
ll heightPrime[N + 1];

vector<ll> collapsedPrimeAdj[N + 1];
bool included[M];

ll getRootPrime(ll u) {
	ll r = rootPrime[u];
	if(r == u) {
		return u;
	}
	rootPrime[u] = getRootPrime(r);
	return rootPrime[u];
}

void mergePrime(ll u, ll v) {
	ll r = getRootPrime(u);
	ll s = getRootPrime(v);
	if(r == s) {
		return;
	}
	if(heightPrime[r] > heightPrime[s]) {
		rootPrime[s] = r;
	} else if(heightPrime[r] < heightPrime[s]) {
		rootPrime[r] = s;
	} else {
		rootPrime[s] = r;
		heightPrime[r]++;
	}
}

ll dst;
bool reachable(ll src, ll prv) {
	if(src == dst) {
		return true;
	}
	for(ll nxt : collapsedPrimeAdj[src]) {
		if(nxt == prv) {
			continue;
		}
		if(reachable(nxt, src)) {
			return true;
		}
	}
	return false;
}

int main() {
	// freopen("in", "r", stdin);
	// freopen("out", "w", stdout);
	// ll T = clock();
	ll n, m; cin >> n >> m;
	ll XOR = 0;
	for(ll e = 0; e < m; e++) {
		ll u, v, w; cin >> u >> v >> w;
		adj[u].pb(v);
		adj[v].pb(u);
		edges.pb(mp(w, mp(u, v)));
		XOR ^= w;
	}
	ll pivot = -1, minCardinality = INFL;
	for(ll u = 1; u <= n; u++) {
		if(adj[u].size() < minCardinality) {
			minCardinality = adj[u].size();
			pivot = u;
		}
	}
	for(ll u = 1; u <= n; u++) {
		rootPrime[u] = pivot;
	}
	heightPrime[pivot] = 1;
	set<pll> adjPivotEdgesPrime; adjPivotEdgesPrime.clear();
	for(ll u : adj[pivot]) {
		for(ll v : adj[pivot]) {
			if(v == u) {
				continue;
			}
			adjPivotEdgesPrime.insert(mp(u, v));
		}
		for(ll v : adj[u]) {
			adjPivotEdgesPrime.erase(mp(u, v));
		}
		rootPrime[u] = u;
		heightPrime[u] = 0;
	}
	for(pll uv : adjPivotEdgesPrime) {
		mergePrime(uv.F, uv.S);
	}
	ll sizePivotPrimeComp = n - adj[pivot].size();
	vector<ll> toMergeWithPivotPrimeComp; toMergeWithPivotPrimeComp.clear();
	for(ll u : adj[pivot]) {
		ll cardinalityWithPivotPrimeComp = 0;
		for(ll v : adj[u]) {
			if(rootPrime[v] == pivot) {
				cardinalityWithPivotPrimeComp++;
			}
		}
		assert(cardinalityWithPivotPrimeComp <= sizePivotPrimeComp);
		if(cardinalityWithPivotPrimeComp < sizePivotPrimeComp) {
			toMergeWithPivotPrimeComp.pb(u);
		}
	}
	for(ll u : toMergeWithPivotPrimeComp) {
		mergePrime(u, pivot);
	}
	ll numCompPrime = 0;
	for(ll u = 1; u <= n; u++) {
		if(rootPrime[u] == u) {
			numCompPrime++;
		}
	}
	ll mstWeight = 0, mergers = 0;
	sort(edges.begin(), edges.end());
	for(ll e = 0; e < edges.size(); e++) {
		auto edge = edges[e];
		ll w = edge.F, u = edge.S.F, v = edge.S.S;
		ll r = getRootPrime(u), s = getRootPrime(v);
		if(r == s) {
			continue;
		}
		collapsedPrimeAdj[u].pb(v);
		collapsedPrimeAdj[v].pb(u);
		mergePrime(r, s);
		mstWeight += w;
		mergers++;
		included[e] = true;
	}
	assert(mergers == numCompPrime - 1);
	if(n * (n - 1) / 2 - m > n - numCompPrime) {
		cout << mstWeight << endl;
		return 0;
	}
	assert(n * (n - 1) / 2 - m == n - numCompPrime);
	ll compensation = INFL;
	for(ll e = 0; e < edges.size(); e++) {
		if(included[e]) {
			continue;
		}
		auto edge = edges[e];
		ll w = edge.F, u = edge.S.F, v = edge.S.S;
		dst = v;
		if(reachable(u, 0)) {
			continue;
		}
		compensation = w;
		break;
	}
	cout << min(mstWeight + compensation, mstWeight + XOR) << endl;
	// cout << (clock() - T) / (double)CLOCKS_PER_SEC << endl;
}