#include <bits/stdc++.h>
using namespace std;
const long long N = 1010;
const long long inf = 1e18;
long long n, m, a[N], b[N], c[N], tot = 0, p = 0, fa[N], now = 0, ans = inf,
                                  sum = 0, vis[N], pre[N], tag[N], dep[N];
struct E {
  long long u, v, w, id;
} e[N];
bool cmp(const E x, const E y) { return x.w > y.w; }
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return f * x;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  return;
}
inline long long getfa(long long x) {
  return (x == fa[x]) ? x : (fa[x] = getfa(fa[x]));
}
inline void dfs(int u) {
  for (register long long i = (1); i <= (m); i++)
    if (vis[i])
      if (e[i].u == u || e[i].v == u) {
        int v = e[i].u + e[i].v - u;
        if (v == pre[u]) continue;
        dep[v] = dep[u] + 1;
        pre[v] = u;
        dfs(v);
      }
  return;
}
inline int check(int u, int v) {
  int ccc = 0;
  if (dep[u] < dep[v]) swap(u, v);
  while (dep[u] != dep[v]) ccc += tag[u], u = pre[u];
  if (u == v) {
    if (ccc) return 0;
    return 1;
  }
  while (pre[u] != pre[v]) ccc += tag[u], ccc += tag[v], u = pre[u], v = pre[u];
  ccc += tag[pre[u]];
  if (ccc) return 0;
  return 1;
}
inline void Kruscal() {
  for (register long long i = (1); i <= (n); i++) fa[i] = i;
  int now = 0, p = 0, tmpsum = 0;
  for (register long long i = (1); i <= (m); i++)
    vis[i] = pre[i] = tag[i] = dep[i] = 0;
  while (now < n - 1) {
    p++;
    int u = e[p].u, v = e[p].v, w = e[p].w;
    int fu = getfa(u), fv = getfa(v);
    if (fu == fv) continue;
    fa[fu] = fv;
    now++;
    vis[p] = 1;
    tmpsum += w;
  }
  dfs(1);
  now = n;
  while (now) tag[now] = 1, now = pre[now];
  for (register long long i = (1); i <= (m); i++)
    if (!vis[i])
      if (check(e[i].u, e[i].v)) tmpsum += e[i].w;
  ans = min(ans, tot - tmpsum);
  return;
}
inline void work() {
  sort(e + 1, e + m + 1, cmp);
  Kruscal();
  random_shuffle(e + 1, e + m + 1);
  Kruscal();
  return;
}
int main() {
  srand((unsigned)time(0));
  n = read(), m = read();
  for (register long long i = (1); i <= (m); i++)
    a[i] = read(), b[i] = read(), c[i] = read(),
    e[i] = (E){a[i], b[i], c[i], i}, tot += c[i];
  while ((double)clock() / CLOCKS_PER_SEC < 3.3) work();
  write(ans);
  return 0;
}
