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 rep(i, j, k) for (LL i = j; i < k; ++i)
#define rep_r(i, j, k) for (LL i = j - 1; i >= k; --i)
#define fast_cin() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long int LL;
typedef pair<int, int> pii;
#define F first
#define S second
#define Edge pair<int, pair<int, int>>
#define MakeEdge(u, v, w) make_pair(w, make_pair(u, v))

#define N 1123456

struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;

    LCA(vector<vector<int>> &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int>> &adj, int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }

    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;

        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};


int UFrnk[N];
int UFpar[N];

inline int Find(int x) {
    int ret = x;
    if (UFpar[x] != x) {
        ret = Find(UFpar[x]);
    }
    UFpar[x] = ret;
    return ret;
}

inline void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (UFrnk[x] > UFrnk[y]) swap(x, y);
    UFrnk[y] += UFrnk[x];
    UFpar[x] = y;
}

int n, m;
Edge posEdges[N];
vector<int> posAdj[N];
set<int> available_nodes;
bool zeroDone[N];
vector<int> mstAdj[N];
bool alive[N];

inline void rangeZeroDFS(int l, int r, int root);

inline void zeroDFS(int u, int root) {
    sort(posAdj[u].begin(), posAdj[u].end());
    posAdj[u].push_back(n);
    available_nodes.erase(u);
    zeroDone[u] = true;
    Union(u, root);
    rangeZeroDFS(0, posAdj[u][0] - 1, root);
    rep (i, 0, posAdj[u].size() - 1) {
        rangeZeroDFS(posAdj[u][i] + 1, posAdj[u][i + 1] - 1, root);
    }
}

inline LL FindSimpleMST() {
    rep (i, 0, n + 1) available_nodes.insert(i);
    rep (i, 0, n) {
        if (!zeroDone[i]) {
            zeroDFS(i, i);
        }
    }
    LL ret = 0;
    rep (i, 0, m) {
        int u = posEdges[i].S.F;
        int v = posEdges[i].S.S;
        int w = posEdges[i].F;
        if (Find(u) != Find(v)) {
            ret += w;
            Union(u, v);
        }
    }
    return ret;
}

#define N2 700

int adj[N2][N2];
bool zeroEdgeExists[N2][N2];
bool vis[N2];

inline void dfs(int u, int root, bool zeroFound) {
    vis[u] = true;
    zeroEdgeExists[root][u] = zeroFound;
    if (root == 227) {
        cout << u << endl;
    }
    rep (i, 0, mstAdj[u].size()) {
        int v = mstAdj[u][i];
        if (root == 227) {
            cout << u << " " << v << endl;
        }
        if (vis[v] == false) {
            dfs(v, root, zeroFound | (adj[u][v] == 0  ? 1 : 0));
        }
    }
}

inline void solve () {
    int xorValue = 0;
    cin >> n >> m;
    rep (i, 0, m) {
        int u, v, w;
        cin >> u >> v >> w;
        xorValue ^= w;
        u--;
        v--;
        posEdges[i] = MakeEdge(u, v, w);
        posAdj[u].push_back(v);
        posAdj[v].push_back(u);
    }
    sort(posEdges, posEdges + m);
    if (LL(n) * LL(n - 1) / 2 - m >= n) {
        cout << FindSimpleMST() << endl;
        return;
    }
    rep (i, 0, m) {
        int u = posEdges[i].S.F;
        int v = posEdges[i].S.S;
        int w = posEdges[i].F;
        adj[u][v] = w;
        adj[v][u] = w;
    }
    rep (i, 0, n) {
        UFpar[i] = i;
        UFrnk[i] = 1;
    }
    int zeroCnt = 0;
    rep (u, 0, n) {
        rep (v, u + 1, n) {
            if (adj[u][v] == 0) {
                if (Find(u) == Find(v)) {
                    cout << FindSimpleMST() << endl;
                    return;
                }
                mstAdj[u].push_back(v);
                mstAdj[v].push_back(u);
                Union(u, v);
                zeroCnt++;
            }
        }
    }
    LL ans = xorValue;
    rep (i, 0, m) {
        int u = posEdges[i].S.F;
        int v = posEdges[i].S.S;
        int w = posEdges[i].F;
        if (Find(u) != Find(v)) {
            ans += w;
            Union(u, v);
            mstAdj[u].push_back(v);
            mstAdj[v].push_back(u);
        } else {
            alive[i] = true;
        }
    }
    rep (i, 0, n) {
        memset(vis, sizeof vis, false);
        dfs(i, i, false);
    }
    rep (i, 0, m) {
        if (alive[i]) {
            int u = posEdges[i].S.F;
            int v = posEdges[i].S.S;
            int w = posEdges[i].F;
            if (n == 633 && w == 2878) {
                cout << i << " " << u << " " << v << " " << Find(u) << " " << Find(v) << endl;
                cout << zeroEdgeExists[u][v] << endl;
            }
            if (zeroEdgeExists[u][v] && w < xorValue) {
                ans += w - xorValue;
                break;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    fast_cin();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

inline void rangeZeroDFS(int l, int r, int root) {
    if (l > r) return;
    while (true) {
        int x = *available_nodes.lower_bound(l);
        if (x > r) return;
        zeroDFS(x, root);
    }
}