#include <bits/stdc++.h>
int N, M, g[15][15], f[32768][15];
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0, u, v, w; i < M; i++) {
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    g[u][v] = g[v][u] = w;
  }
  for (int i = 0; i < 1 << N; i++)
    for (int j = 0; j < N; j++) f[i][j] = 2000000000;
  for (int i = 1; i < 1 << N; i += 2) f[i][0] = 0;
  for (int i = 1; i < 1 << N; i++)
    for (int j = 0; j < N; j++)
      if (f[i][j] < 2000000000) {
        static int s[15];
        for (int k = 0; k < N; k++) {
          s[k] = 0;
          for (int l = 0; l < N; l++)
            if (i >> l & 1) s[k] += g[k][l];
        }
        for (int k = 0; k < N; k++)
          if (!(i >> k & 1) && g[j][k])
            for (int mask = i | 1 << k, l = mask; l < 1 << N;
                 l = l + 1 | mask) {
              int S = -g[j][k];
              for (int m = 0; m < N; m++)
                if (l - i >> m & 1) S += s[m];
              f[l][k] = std::min(f[l][k], f[i][j] + S);
            }
      }
  printf("%d\n", f[(1 << N) - 1][N - 1]);
  return 0;
}
