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;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
mt19937_64 rnd(736);
template <typename T>
void read(T& x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
template <typename T, typename... Args>
void read(T& first, Args&... args) {
  read(first);
  read(args...);
}
int n, m, u[200020], v[200020], w[200020], cnt0[200020];
struct edge {
  int u, v, w, ty;
  bool operator<(const edge& rhs) const { return w < rhs.w; }
};
set<int> cont[200020];
vector<pair<int, int> > G[200020];
int dis[1010][1010];
int bcj[200020];
long long ddd[200020];
int fnd(int x) {
  if (bcj[x] == x) {
    return x;
  } else {
    int u = fnd(bcj[x]);
    ddd[x] ^= ddd[bcj[x]];
    return bcj[x] = u;
  }
}
void solve1() {
  int thr = (n - 2) / 2;
  vector<int> V;
  for (int i = 1; i <= n; i++) {
    if (cont[i].size() < thr)
      V.push_back(i);
    else {
      for (int j = 1; j <= n; j++) {
        if (!cont[i].count(j)) {
          int a = fnd(i), b = fnd(j);
          if (a != b) bcj[a] = b;
        }
      }
    }
  }
  for (int i = 0; i < V.size() - 1; i++) {
    int a = fnd(V[i]), b = fnd(V[i + 1]);
    if (a != b) bcj[a] = b;
  }
  vector<edge> V2;
  for (int i = 0; i < m; i++) {
    V2.push_back((edge){u[i], v[i], w[i], 0});
  }
  sort(V.begin(), V.end());
  long long ans = 0;
  for (auto ct : V2) {
    if (fnd(ct.u) == fnd(ct.v)) continue;
    int a = fnd(ct.u), b = fnd(ct.v);
    bcj[a] = b;
    if (ct.ty) ddd[a] = rnd();
    ans += ct.w;
  }
  cout << ans << endl;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) bcj[i] = i;
  int q = 0;
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> w[i];
    cont[u[i]].insert(v[i]);
    cont[v[i]].insert(u[i]);
    cnt0[u[i]] += 1;
    cnt0[v[i]] += 1;
    q ^= w[i];
  }
  int cc = 0;
  for (int i = 1; i <= n; i++) {
    if (cnt0[i] != n - 1) cc += 1;
  }
  if (n * (n - 1) / 2 - m >= cc) {
    solve1();
    return 0;
  }
  for (int i = 0; i < m; i++) {
    dis[u[i]][v[i]] = w[i];
    dis[v[i]][u[i]] = w[i];
  }
  vector<edge> V;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (!dis[u[i]][v[i]]) {
        V.push_back((edge){i, j, 0, 1});
      } else {
        V.push_back((edge){i, j, dis[i][j], 0});
      }
    }
  }
  sort(V.begin(), V.end());
  long long ans = 0;
  for (auto ct : V) {
    if (fnd(ct.u) == fnd(ct.v)) continue;
    int a = fnd(ct.u), b = fnd(ct.v);
    bcj[a] = b;
    if (ct.ty) ddd[a] = rnd();
    ans += ct.w;
  }
  long long c = q;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (dis[u[i]][v[i]]) {
        fnd(u[i]);
        fnd(v[i]);
        if (ddd[u[i]] != ddd[v[i]]) c = min(c, 1ll * dis[u[i]][v[i]]);
      }
    }
  }
  ans += c;
  cout << ans << endl;
  return 0;
}
