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 int long long
void read (int &x) {
    char ch = getchar(); int f = 0; x = 0;
    while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    if (f) x = -x;
} const int N = 2e5 + 5, M = N << 1;
int n, m, cc, fa[N], s, sz[N];
struct edge {
    int u, v, w;
    bool operator < (const edge &x) const {
        return w < x.w;
    }
} a[N];
int get (int x) { return fa[x] == x ? x : fa[x] = get (fa[x]); }
void merge (int x, int y) {
    int fx = get (x), fy = get (y);
    if (fx == fy) return;
    if (sz[fx] < sz[fy]) sz[fy] += sz[fx], fa[fx] = fy;
    else sz[fx] += sz[fy], fa[fy] = fx;
}
unordered_map<int, int> mp[N]; int vis1[N], vis2[N];
vector<int> g[N]; queue <int> q;
struct link{int pre, nxt; } L[N];
void del(int x) {
    L[L[x].pre].nxt = L[x].nxt; L[L[x].nxt].pre = L[x].pre;
}
void bfs () {
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    memset (vis1, 0, sizeof (vis1));
    memset (vis2, 0, sizeof (vis2));
    for (int i = 1; i <= n; ++i)
        L[i - 1].nxt = i, L[i].pre = i - 1;
    L[n].nxt = 0;
    while (L[0].nxt) {
        int now = L[0].nxt; del (now);
        q.push (now); vis2[now] = 1;
        while (!q.empty ()) {
            int u = q.front(); q.pop(); merge (u, now);
            for (int i : g[u]) vis1[i] = 1;
            for (int i = L[0].nxt; i; i = L[i].nxt)
                if (!vis1[i] && !vis2[i]) vis2[i] = 1, q.push (i), del (i);
            for (int i : g[u]) vis1[i] = 0;
        }
    }
}
signed main() {
    read (n), read (m); s = n * (n - 1) / 2 - m;
    for (int i = 1; i <= m; ++i) {
        read (a[i].u), read (a[i].v), read (a[i].w);
        g[a[i].u].push_back (a[i].v);
        g[a[i].v].push_back (a[i].u);
        cc ^= a[i].w;
        mp[a[i].u][a[i].v] = mp[a[i].v][a[i].u] = 1;
    }
    sort (a + 1, a + m + 1);
    if (s >= n) {
        bfs (); int ans = 0;
        for (int i = 1; i <= m; ++i) {
            int x = a[i].u, y = a[i].v;
            int fx = get (x), fy = get (y);
            if (fx != fy) fa[fx] = fy, ans += a[i].w;
        }
        printf ("%lld\n", ans);
    } else { //
        // puts ("233");
        int res = 6e18;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j) {
                if (mp[i].count (j)) continue;
                // printf ("%lld %lld\n", i, j);
                int ans = 0, tag = 0;
                edge tmp = {i, j, cc};
                g[i].push_back (j), g[j].push_back (i);
                bfs (); a[m + 1].w = 3e9;
                if (a[1].w >= tmp.w) {
                    tag = 1;
                    int x = tmp.u, y = tmp.v; tag = 1;
                    int fx = get (x), fy = get (y);
                    if (fx == fy) continue; ans += tmp.w;
                    if (sz[fx] < sz[fy]) sz[fy] += sz[fx], fa[fx] = fy;
                    else sz[fx] += sz[fy], fa[fy] = fx;
                }
                for (int j = 1; j <= m; ++j) {
                    int x = a[j].u, y = a[j].v;
                    int fx = get (x), fy = get (y);
                    if (fx != fy){
                        ans += a[j].w;
                        if (sz[fx] < sz[fy]) sz[fy] += sz[fx], fa[fx] = fy;
                        else sz[fx] += sz[fy], fa[fy] = fx;
                    }
                    if (!tag && a[j].w <= tmp.w && a[j + 1].w >= tmp.w) {
                        x = tmp.u, y = tmp.v; tag = 1;
                        fx = get (x), fy = get (y);
                        if (fx == fy) continue; ans += tmp.w;
                        if (sz[fx] < sz[fy]) sz[fy] += sz[fx], fa[fx] = fy;
                        else sz[fx] += sz[fy], fa[fy] = fx;
                    }
                }
                g[i].pop_back (), g[j].pop_back ();
                res = min (res, ans);
            }
        printf ("%lld\n", res);
    }
    return 0;
}
