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 int long long
#define dbg(x) cerr << #x << " = " << x << endl
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
#define sz(x) (x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int N = 234567;
int pa[N];
int f(int x)
{
	if (pa[x] == x) return x;
	return pa[x] = f(pa[x]); 
}
 
std::vector<int> g[N];
bool in[N], vis[N];
int nxt[N], prv[N], n, m;
int stk[N], p;
void del(int i) {
    nxt[prv[i]] = nxt[i];
    prv[nxt[i]] = prv[i];
}
void dfs(int s) {
    p = 0, stk[p++] = s;
    while(p) {
        int i = stk[--p];
        for(int j: g[i]) in[j] = true;
        for(int i = nxt[0]; i <= n; i = nxt[i]) if(!in[i]) {
            if (!vis[i]) pa[i] = s;
						vis[i] = true;
            del(i);
            stk[p++] = i;
        }
        for(int j: g[i]) in[j] = false;
    }
}
vector<pair<int, pii> > ee;
int fu[N];
main(){
	ios::sync_with_stdio(false);cin.tie (0);
	int x,y,z;cin >> n >> m;vpii e;
	for (int i = 1; i <= n; ++i) pa[i] = i;
	int xx = 0;
	for(int i=0;i<m;++i)
	{cin >> x >> y >> z;
	g[x].push_back(y), g[y].push_back(x);
		//E[x].pb(mp(y, z)); E[y].pb(mp(x, z));
		ee.pb(mp(z, mp(x,y)));
		//dbg(x); dbg(y);
		xx ^= z;
	}
	
	int cnt = 0;
    nxt[0] = 1;
    for(int i = 1; i <= n; i++) nxt[i] = i+1, prv[i] = i-1;
    for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i), ++cnt;
  //dbg(cnt);
  //for (int i = 1; i <= n; ++i) cout << pa[i] << '\n';
  
	sort(ee.begin(), ee.end());
	int com = 1, mn = 123456789123456ll;
	int ans = 0;
	for (int i = 1; i <= n; ++i) fu[i] = f(i);
	for (auto x : ee)
	{
		if (f(x.S.F) != f(x.S.S)) 
		{
			pa[f(x.S.F)] = f(x.S.S);
			ans += x.F;
			++com;
		} else if (x.F < mn) mn = x.F;
	}
	//dbg(com);
	if (n * (n - 1) / 2 - m > n - cnt) cout << ans << '\n';
	else cout << ans + min(mn, xx) << '\n';
	return 0;
}