#include <bits/stdc++.h>
using namespace std;
int f[20][70005], g[70005];
int con[20][20];
inline int lowbit(int x) { return x & (-x); }
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int tot = 0;
  for (int i = (1); i <= (m); i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    con[x][y] = con[y][x] = z;
    tot += z;
  }
  memset(f, -1, sizeof(f));
  f[1][1] = 0;
  for (int i = (1); i <= ((1 << n) - 1); i++)
    for (int j = (1); j <= (n); j++)
      if ((1 << (j - 1)) & i)
        for (int k = (j + 1); k <= (n); k++)
          if ((1 << (k - 1)) & i) g[i] += con[j][k];
  for (int i = (1); i <= (n); i++) {
    for (int j = (0); j <= ((1 << n) - 1); j++)
      if (f[i][j] >= 0) {
        int k = ((1 << n) - 1) ^ j;
        for (int p = k; p; p = (p - 1) & k) {
          if (!p) continue;
          for (int nxt = (1); nxt <= (n); nxt++)
            if ((1 << (nxt - 1)) & p && con[i][nxt]) {
              f[nxt][j | p] = max(f[nxt][j | p], f[i][j] + con[i][nxt] + g[p]);
            }
        }
      }
  }
  int ans = 0;
  for (int i = (1); i <= ((1 << n) - 1); i++) ans = max(ans, f[n][i]);
  printf("%d\n", tot - ans);
  return 0;
}
