#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = 1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + ch - 48;
  return f ? -x : x;
}
long long n, m, G[20][20], f[1 << 20][20], s[1 << 20], sum;
int main() {
  n = read();
  m = read();
  for (long long i = 1; i <= m; ++i) {
    long long x = read() - 1, y = read() - 1;
    G[x][y] = G[y][x] = read();
    sum += G[x][y];
  }
  for (long long i = 0; i <= 1 << n; ++i)
    for (long long j = 0; j <= n; ++j)
      if ((i >> j) & 1)
        for (long long k = j + 1; k <= n; ++k)
          if ((i >> k) & 1) s[i] += G[j][k];
  for (long long i = 0; i <= 1 << n; ++i)
    for (long long j = 0; j <= n; ++j) f[i][j] = -1e9;
  for (long long i = 0; i <= 1 << n; ++i)
    if (i & 1) f[i][0] = s[i];
  for (long long i = 0; i <= 1 << n; ++i)
    for (long long j = 0; j <= n; ++j)
      if ((i >> j) & 1)
        for (long long k = i; k; k = (k - 1) & i)
          if (k & 1)
            for (long long l = 0; l <= n; ++l)
              if (((k >> l) & 1) && ((~k >> j) & 1) && G[l][j])
                f[i][j] = max(f[i][j], f[k][l] + G[l][j] + s[i ^ k]);
  printf("%d\n", sum - f[(1 << n) - 1][n - 1]);
  return 0;
}
