#include <bits/stdc++.h>
using namespace std;
const int N = 21;
const int N0 = 33000;
int g[N][N], t0[N0], t1[N0][N], n, m;
int f[N][N0][2];
int cut(int s1, int s2) { return t0[s1 | s2] - t0[s1] - t0[s2]; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    g[x][y] += z, g[y][x] += z;
  }
  for (int i = 0; i <= (1 << n) - 1; i++) {
    for (int j = 1; j <= n; j++)
      if (i & (1 << (j - 1))) {
        for (int k = j; k <= n; k++)
          if (i & (1 << (k - 1))) t0[i] += g[j][k];
        for (int k = 1; k <= n; k++) t1[i][k] += g[k][j];
      }
  }
  for (int i = 1; i <= n; i++)
    for (int s = 0; s <= (1 << n) - 1; s++)
      f[i][s][0] = f[i][s][1] = 2100000000;
  f[1][1][0] = 0;
  for (int s = 0; s <= (1 << n) - 1; s++)
    for (int i = 1; i <= n; i++)
      if (s & (1 << (i - 1))) {
        int tmp = s ^ (1 << (i - 1));
        for (int j = 1; j <= n; j++)
          if ((tmp & (1 << (j - 1))) && g[i][j]) {
            f[i][s][0] = min(f[i][s][0], f[j][tmp][1] - g[i][j] + t1[tmp][i]);
          }
        for (int s0 = tmp;; s0 = tmp & (s0 - 1)) {
          f[i][s][1] = min(f[i][s][1], f[i][s ^ s0][0] + cut(s0, tmp ^ s0));
          if (!s0) break;
        }
      }
  printf("%d\n", f[n][(1 << n) - 1][1]);
  return 0;
}
