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;
struct Edge {
  int u, v, w;
  friend bool operator<(Edge x1, Edge x2) { return x1.w < x2.w; }
} num[200005];
int d[200005], rt[200005];
vector<int> ask, vec[705];
map<int, bool> mp[200005];
int cnt = 0;
int maps[705][705], dis[705], fr[705][15], dep[705];
bool life[705], wtf[705][15];
int findr(int x) {
  if (rt[x] == x)
    return x;
  else
    return rt[x] = findr(rt[x]);
}
void dfs(int x) {
  for (int i = 1; i <= 10; i++) {
    fr[x][i] = fr[fr[x][i - 1]][i - 1];
    wtf[x][i] = wtf[x][i - 1] | wtf[fr[x][i - 1]][i - 1];
  }
  for (int i = 0; i < vec[x].size(); i++) dfs(vec[x][i]);
}
bool ok(int u, int v) {
  bool f = 0;
  for (int i = 10; i >= 0; i--) {
    if (dep[fr[u][i]] >= dep[v]) {
      f |= wtf[u][i];
      u = fr[u][i];
    }
    if (dep[fr[v][i]] >= dep[u]) {
      f |= wtf[v][i];
      v = fr[v][i];
    }
  }
  for (int i = 10; i >= 0; i--) {
    if (fr[u][i] != fr[v][i]) {
      f |= wtf[u][i];
      f |= wtf[v][i];
      u = fr[u][i];
      v = fr[v][i];
    }
  }
  if (u != v) {
    f |= wtf[u][0];
    f |= wtf[v][0];
  }
  return f;
}
int main() {
  int n, m, tp, minn, nu, nv;
  long long ans = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &num[i].u, &num[i].v, &num[i].w);
  if (n <= 650) {
    cnt = (n * (n - 1)) / 2 - m;
    for (int i = 1; i <= m; i++)
      maps[num[i].u][num[i].v] = maps[num[i].v][num[i].u] = num[i].w;
    life[1] = 1;
    dep[1] = 1;
    dis[1] = 0;
    for (int i = 2; i <= n; i++) {
      dis[i] = maps[1][i];
      fr[i][0] = 1;
    }
    for (int ts = 2; ts <= n; ts++) {
      minn = 2 * 998244353;
      for (int i = 1; i <= n; i++) {
        if (life[i] == 0 && dis[i] < minn) {
          minn = dis[i];
          tp = i;
        }
      }
      life[tp] = 1;
      ans += dis[tp];
      vec[fr[tp][0]].push_back(tp);
      dep[tp] = dep[fr[tp][0]] + 1;
      if (dis[tp] == 0) {
        cnt--;
        wtf[tp][0] = 1;
      }
      for (int i = 1; i <= n; i++) {
        if (i != tp && maps[tp][i] < dis[i]) {
          dis[i] = maps[tp][i];
          fr[i][0] = tp;
        }
      }
    }
    if (cnt == 0) {
      tp = 0;
      minn = 2 * 998244353;
      dfs(1);
      for (int i = 1; i <= m; i++) {
        tp ^= num[i].w;
        if (fr[num[i].u][0] != num[i].v && fr[num[i].v][0] != num[i].u &&
            ok(num[i].u, num[i].v))
          minn = min(minn, num[i].w);
      }
      ans += min(minn, tp);
    }
  } else {
    for (int i = 1; i <= m; i++) {
      d[num[i].u]++;
      d[num[i].v]++;
      mp[num[i].u][num[i].v] = 1;
      mp[num[i].v][num[i].u] = 1;
    }
    minn = n + 5;
    for (int i = 1; i <= n; i++) {
      if (d[i] < minn) {
        minn = d[i];
        tp = i;
      }
    }
    rt[tp] = tp;
    for (int i = 1; i <= n; i++) {
      if (i != tp) {
        if (mp[tp].count(i) == 0)
          rt[i] = tp;
        else {
          ask.push_back(i);
          rt[i] = i;
        }
      }
    }
    for (int i = 0; i + 1 < ask.size(); i++) {
      for (int j = i + 1; j < ask.size(); j++) {
        nu = findr(ask[i]);
        nv = findr(ask[j]);
        if (nu != nv && mp[ask[i]].count(ask[j]) == 0) rt[nv] = nu;
      }
    }
    for (int i = 0; i < ask.size(); i++) {
      nu = findr(ask[i]);
      for (int j = 1; j <= n && rt[nu] != tp; j++)
        if (rt[j] == tp && mp[j].count(ask[i]) == 0) rt[nu] = tp;
    }
    sort(num, num + m);
    for (int i = 0; i < cnt; i++) {
      nu = findr(num[i].u);
      nv = findr(num[i].v);
      if (nu != nv) {
        ans += num[i].w;
        rt[nv] = nu;
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}
