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;
long long INF = 1e9 + 7;
long long MOD = 998244353;
void YESNO(long long a) { cout << (a ? "YES" : "NO") << "\n"; }
long long par[200005];
long long find_par(long long x) {
  if (par[x] == x) {
    return x;
  }
  return par[x] = find_par(par[x]);
}
bool enose(long long x, long long y) {
  long long p1 = find_par(x);
  long long p2 = find_par(y);
  par[p2] = p1;
  return p1 != p2;
}
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  set<pair<long long, pair<long long, long long> > > edges;
  long long x = 0;
  long long l = n * (n - 1);
  l /= 2;
  set<pair<long long, long long> > ip;
  set<long long> P;
  for (long long i = 1; i < n + 1; i++) {
    P.insert(i);
  }
  set<long long> adj[n + 1];
  for (long long i = 0; i < m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    if (b < a) {
      swap(a, b);
    }
    edges.insert(pair<long long, pair<long long, long long> >(
        c, pair<long long, long long>(a, b)));
    adj[b].insert(a);
    ip.insert(pair<long long, long long>(a, b));
    l--;
    x ^= c;
  }
  long long ans = 1e18;
  if (l >= n) {
    ans = 0;
    for (long long i = 1; i < n + 1; i++) {
      par[i] = i;
    }
    for (long long i = 1; i < n + 1; i++) {
      vector<long long> fk;
      for (auto E : P) {
        if (E == i) {
          break;
        }
        if (!adj[i].count(E)) {
          fk.push_back(E);
          enose(i, E);
        }
      }
      fk.push_back(i);
      for (long long j = 1; j < fk.size(); j++) {
        P.erase(fk[j]);
      }
    }
    for (auto x : edges) {
      if (find_par(x.second.first) != find_par(x.second.second)) {
        enose(x.second.first, x.second.second);
        ans += x.first;
      }
    }
  } else {
    long long aa, bb;
    ans = 1e18;
    vector<pair<long long, long long> > ex;
    for (long long i = 0; i < n; i++) {
      for (long long j = i + 1; j < n; j++) {
        if (!ip.count(pair<long long, long long>(i + 1, j + 1))) {
          ex.push_back(pair<long long, long long>(i + 1, j + 1));
          edges.insert(pair<long long, pair<long long, long long> >(
              0, pair<long long, long long>(i + 1, j + 1)));
        }
      }
    }
    for (auto X : ex) {
      aa = X.first, bb = X.second;
      edges.erase(pair<long long, pair<long long, long long> >(
          0, pair<long long, long long>(aa, bb)));
      edges.insert(pair<long long, pair<long long, long long> >(
          x, pair<long long, long long>(aa, bb)));
      long long res = 0;
      for (long long i = 1; i < n + 1; i++) {
        par[i] = i;
      }
      long long ev = 0;
      for (auto x : edges) {
        if (find_par(x.second.first) != find_par(x.second.second)) {
          enose(x.second.first, x.second.second);
          res += x.first;
          ev++;
          if (ev == n - 1) {
            break;
          }
        }
      }
      edges.erase(pair<long long, pair<long long, long long> >(
          x, pair<long long, long long>(aa, bb)));
      edges.insert(pair<long long, pair<long long, long long> >(
          0, pair<long long, long long>(aa, bb)));
      ans = min(ans, res);
    }
  }
  cout << ans << "\n";
}
