#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int p[N], a[N][N];
struct A {
  int x, y, v;
  bool operator<(const A& a) const { return v > a.v; }
} b[N];
int T[N], c[N], ans = 0, n, sum = 0;
int findr(int x) {
  if (T[x] == -1)
    return x;
  else
    return T[x] = findr(T[x]);
}
void calc() {
  int i, j, k = 0, e = 0, pp, qq, tmp = 0, sss = 0;
  for (i = 2; i <= n - 1; i++)
    if (c[i] == 0) p[++k] = i;
  p[++k] = 1;
  p[++k] = n;
  for (i = 1; i <= k; i++)
    for (j = 1; j <= k; j++)
      if (i != j && a[p[i]][p[j]]) b[++e] = (A){p[i], p[j], a[p[i]][p[j]]};
  sort(b + 1, b + e + 1);
  for (i = 1; i <= n; i++) T[i] = -1;
  for (i = 1; i <= e; i++) {
    pp = findr(b[i].x);
    qq = findr(b[i].y);
    if (pp != qq) T[pp] = qq, tmp += b[i].v, sss++;
  }
  if (sss < k - 1) return;
  for (i = 2; i <= n - 1; i++)
    for (j = i + 1; j <= n - 1; j++)
      if (c[i] == c[j] && c[i]) tmp += a[i][j];
  for (i = 2; i <= n - 1; i++) {
    if (c[i] == 1) tmp += a[1][i];
    if (c[i] == 2) tmp += a[n][i];
  }
  if (tmp > ans) ans = tmp;
}
void dfs(int x) {
  if (x == n) {
    calc();
    return;
  }
  c[x] = 0;
  dfs(x + 1);
  c[x] = 1;
  dfs(x + 1);
  c[x] = 2;
  dfs(x + 1);
}
int main() {
  int i, x, y, c, m;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d %d %d", &x, &y, &c);
    a[x][y] = a[y][x] = c;
    sum += c;
  }
  dfs(2);
  printf("%d\n", sum - ans);
  return 0;
}
