#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15 + 5;
const int ALL = (1 << 15) + 5;
inline void chk_max(int &a, int b) {
  if (a < b) a = b;
}
int lb[ALL];
int g[MAXN][MAXN];
int cost[ALL], f[ALL][MAXN];
int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u][v] = g[v][u] = w;
  }
  int all = (1 << n) - 1;
  for (int mask = 0; mask <= all; ++mask) {
    for (int i = 1; i <= n; ++i)
      if ((((mask) >> (i - 1)) & 1))
        for (int j = 1; j < i; ++j)
          if ((((mask) >> (j - 1)) & 1)) cost[mask] += g[i][j];
  }
  for (int mask = 1; mask <= all; mask += 2)
    for (int i = 1; i <= n; ++i)
      if ((((mask) >> (i - 1)) & 1)) {
        for (int mask2 = mask; mask2; mask2 = (mask2 - 1) & mask) {
          if (!(mask2 & 1)) continue;
          if ((((mask2) >> (i - 1)) & 1)) continue;
          for (int j = 1; j <= n; ++j)
            if ((((mask2) >> (j - 1)) & 1))
              if (g[i][j] > 0)
                chk_max(f[mask][i], f[mask2][j] + g[j][i] + cost[mask ^ mask2]);
        }
      }
  int ans = 0;
  for (int mask = 1; mask <= all; ++mask) chk_max(ans, f[mask][n]);
  printf("%d", cost[all] - ans);
  return 0;
}
