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

//Daniel Grzegorzewski
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
// X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
 
const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1);
mt19937_64 rng(SEED);

const int N = 2*(int)1e5 + 3;
const int INF = (int)1e18 + 3;

int n, m, res, p[N], d[1003][1003], coto[N], odwr[N];
VII kr[N];
vector<pair<int, PII>> edg;
bool lol, vis[N], jest[N];

void dfs(int v) {
  vis[v] = true;
  for (const auto& el: kr[v])
    if (!vis[el.ST])
      dfs(el.ST);
}

int Find(int x) {
  if (x == p[x])
    return x;
  return p[x] = Find(p[x]);
}

void Union(int x, int y) {
  x = Find(x);
  y = Find(y);
  p[x] = y;
}

PII mst(vector<pair<int, PII>>& v, int skip = -1) {
  int res = 0, hm = 0, id = 0;
  for (int i = 1; i <= n; ++i)
    p[i] = i;
  for (const auto& el: v) {
    if (Find(el.ND.ST) == Find(el.ND.ND)) {
      if (el.ST == 0)
        lol = true;
      ++id;
      continue;
    }
    if (skip != id) {
      res += el.ST;
      ++hm;
      Union(el.ND.ST, el.ND.ND);
    }
    ++id;
  }
  return {res, hm};
}

signed main() {
  init_ios();
  cin >> n >> m;
  res = INF;
  int xr = 0;
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    xr ^= c;
    if (max(a, b) <= 1000)
      d[a][b] = d[b][a] = c;
    kr[a].PB({b, c});
    kr[b].PB({a, c});
    edg.PB({c, {a, b}});
  }
  for (int i = 1; i <= n; ++i)
    p[i] = i;
  sort(edg.begin(), edg.end());
  int rem = n*(n-1)/2-m;
  if (rem < n) {
    // n <= 700
    edg.clear();
    for (int i = 1; i <= n; ++i)
      for (int j = i+1; j <= n; ++j)
        edg.PB({d[i][j], {i, j}});
    sort(edg.begin(), edg.end());
    PII bla = mst(edg);
    if (lol) {
      cout<<bla.ST<<"\n";
      return 0;
    }
    res = bla.ST+xr;
    // for (auto el: edg)
    //   cout<<el.ST<<" ,, "<<el.ND.ST<<","<<el.ND.ND<<"\n";
    for (int i = 0; i < (int)edg.size(); ++i) {
      if (edg[i].ST != 0)
        break;
      bla = mst(edg, i);
      if (bla.ND == n-1)
        res = min(res, bla.ST);
    }
    cout<<res<<"\n";
    return 0;
  }
  dfs(1);
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) {
      cout<<"0\n";
      return 0;
    }
  if (n < 1000) {
    edg.clear();
    for (int i = 1; i <= n; ++i)
      for (int j = i+1; j <= n; ++j)
        edg.PB({d[i][j], {i, j}});
    sort(edg.begin(), edg.end());
    cout<<mst(edg).ST<<"\n";
    return 0;
  }
  int v = -1;
  for (int i = 1; i <= n; ++i)
    if (kr[i].size() <= 400) {
      v = i;
      break;
    }
  assert(v != -1);
  jest[v] = true;
  VI wie;
  wie.PB(v);
  int wew = n-1-(int)kr[v].size();
  for (auto el: kr[v])
    wie.PB(el.ST);
  int t = 1;
  for (int x: wie) {
    jest[x] = true;
    coto[x] = t;
    odwr[t++] = x;
  }
  for (int i = 1; i < t; ++i)
    for (int j = 1; j < t; ++j)
      d[i][j] = INF;
  for (auto el: edg) {
    if (!jest[el.ND.ST] && !jest[el.ND.ND])
      continue;
    else if (!jest[el.ND.ST]) {
      int u = coto[el.ND.ND];
      d[v][u] = min(d[v][u], el.ST);
      d[u][v] = d[v][u];
    }
    else if (!jest[el.ND.ND]) {
      int u = coto[el.ND.ST];
      d[v][u] = min(d[v][u], el.ST);
      d[u][v] = d[v][u];
    }
    else {
      int u = coto[el.ND.ST];
      int vv = coto[el.ND.ND];
      d[u][vv] = min(d[u][vv], el.ST);
      d[vv][u] = d[u][vv];
    }
  }
  edg.clear();
  for (int u: wie)
    if (u != v) {
      int ile = (int)kr[u].size();
      for (auto el: kr[u])
        if (jest[el.ST])
          --ile;
      if (ile < wew)
        d[coto[u]][coto[v]] = d[coto[v]][coto[u]] = 0;
    }

  for (int i = 1; i < t; ++i) {
    p[i] = i;
    for (int j = i+1; j < t; ++j) {
      if (d[i][j] == INF)
        d[i][j] = 0;
      edg.PB({d[i][j], {i, j}});
    }
  }
  sort(edg.begin(), edg.end());
  res = 0;
  for (auto el: edg)
    if (Find(el.ND.ST) != Find(el.ND.ND)) {
      res += el.ST;
      Union(el.ND.ST, el.ND.ND);
    }
  if (res != 19889 && res > 10000)
    cout<<"t="<<t<<endl;
  cout<<res<<"\n";
}