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 MAXN 200010
#define INF 1e18
using namespace std;
int M,N,f[MAXN],ret = 0,dp[MAXN];long long sum;
int findf(int x){return f[x] == x ? f[x] : f[x] = findf(f[x]); }
struct node{int f,t,v,flg;friend bool operator <(node a,node b){return a.v < b.v;}};
vector<node>w;
vector<pair<int,int>>e[MAXN];
set<int>s;
map<pair<int,int>,int>m;

namespace LCA{
    int par[MAXN][40],dep[MAXN],lg2[MAXN];
    void dfs(int x,int f){
        par[x][1] = f;
        for(int i = 0;i<(int)e[x].size();i++){
            int to = e[x][i].first;
            if(to == f)continue;
            dep[to] = dep[x] + 1;
            dp[to] = dp[x];
            if(!e[x][i].second)++dp[to];
            dfs(to,x);
        }
    }
    void pre(int n,int r){
        dfs(r,r);
        for(int i = 1; i <= n; ++i)
            lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);//1-index
        for(int j = 2;j <= lg2[n];j++)
            for(int i = 1;i <= n;i++)par[i][j] = par[par[i][j - 1]][j - 1];
    }
    int cal(int u,int v,int n){
        if(dep[u] < dep[v])swap(u,v);
        while(dep[u] > dep[v])u = par[u][lg2[dep[u] - dep[v]]];
        while(u != v){
            int tot = lg2[n];
            while(tot && par[u][tot] == par[v][tot])--tot;
            if(!tot)tot = 1;
            u = par[u][tot],v = par[v][tot];
        }
        return u;
    }
};
void bfs(int x)
{
    s.erase(s.find(x));
    queue<int>q;q.push(x);
    while(!q.empty())
    {
        int x = q.front();q.pop();
        for(auto iter = s.begin();iter!=s.end();)
        {
            int to = *iter;
            if(m[{x,to}]==0)
            {
                e[x].push_back({to,0});
                e[to].push_back({x,0});
                --sum;
                f[findf(x)] = findf(to);
                ++iter;
                s.erase(s.find(to));
                q.push(to);
            }
            else ++iter;
        }
    }
}
int main()
{
    scanf("%d %d",&N,&M);
    sum = (long long)N * (N-1) / 2 - M;
    for(int i=1;i<=N;i++)f[i] = i,s.insert(i);
    for(int i=1;i<=M;i++)
    {
        int u,v,we;scanf("%d %d %d",&u,&v,&we);
        ret ^= we;
        m[{u,v}] = m[{v,u}] = 1;
        w.push_back({u,v,we,0});
    }
    for(int i=1;i<=N;i++)
    {
        if(s.find(i)!=s.end())bfs(i);
    }
    sort(w.begin(),w.end());
    long long sup = 0;
    for(int i=0;i<(int)w.size();i++)
    {
        int u = w[i].f,v = w[i].t,val = w[i].v;
        if(findf(u) == findf(v))continue;
        f[findf(u)] = findf(v);
        sup += val;
        w[i].flg = 1;
        e[u].push_back({v,1});
        e[v].push_back({u,1});
    }
    if(sum)
    {
        cout<<sup<<endl;
        return 0;
    }
    long long anss = ret;
    LCA::pre(N,1);
    for(int i=0;i<(int)w.size();i++)
    {
        if(w[i].flg)continue;
        int u = w[i].f,v = w[i].t,val = w[i].v;
        int id = LCA::cal(u,v,N);
        if(dp[id] < dp[u] || dp[id] < dp[v])
            anss = min(anss,(long long)val);
    }
    cout<<anss + sup<<endl;
    return 0;
}
/*
4 4
2 1 14
1 4 14
3 2 15
4 3 8


*/
