#include <bits/stdc++.h>
using namespace std;
int n, m, map[20][20], x, y, z, w[32770], bin[20], f[32770][20], ans, s, ss;
int main() {
  scanf("%d%d", &n, &m);
  memset(map, 0, sizeof(map));
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    map[x][y] = map[y][x] = z;
  }
  bin[0] = 1;
  for (int i = 1; i <= n; i++) bin[i] = bin[i - 1] << 1;
  for (int i = 0; i <= bin[n] - 1; i++) {
    w[i] = 0;
    for (int j = 1; j <= n; j++)
      if (i & bin[j - 1])
        for (int k = j + 1; k <= n; k++)
          if (i & bin[k - 1]) w[i] += map[j][k];
  }
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= bin[n] - 1; i++)
    if (i & bin[0])
      for (int j = 1; j <= n; j++)
        if (i & bin[j - 1]) {
          if (j == 1) {
            f[i][j] = w[i];
            continue;
          }
          s = i - bin[j - 1];
          for (int k = 1; k <= n; k++)
            if (j != k && i & bin[k - 1] && map[k][j]) {
              x = k >= 2 ? bin[0] + bin[k - 1] : bin[0];
              s -= x;
              for (int s1 = s; s1 >= 0; s1 = (s1 - 1) & s) {
                ss = s1 + x;
                f[i][j] = max(f[i][j], f[ss][k] + w[i - ss] + map[k][j]);
                if (!s1) break;
              }
              s += x;
            }
        }
  ans = -f[bin[n] - 1][n];
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) ans += map[i][j];
  printf("%d", ans);
  return 0;
}
