#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int S = 1 << N;
inline void upd(int& a, int b) {
  if (a < b) a = b;
}
int _w;
int f[N][S], g[S], G[N][N], n, m, sum;
int main(void) {
  _w = scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; ++i) {
    _w = scanf("%d%d%d", &u, &v, &w);
    --u, --v;
    G[u][v] = G[v][u] = w;
    sum += w;
  }
  memset(g, 0xc0, sizeof g);
  for (int i = 0; i < n; ++i) g[(1 << i)] = 0;
  for (int s = 1, tmp; s < (1 << n); ++s)
    if (g[s] >= 0)
      for (int i = 0; i < n; ++i)
        if ((~s >> i) & 1) {
          tmp = 0;
          for (int j = 0; j < n; ++j)
            if (((s >> j)) & 1 && G[i][j] >= 0) tmp += G[i][j];
          upd(g[s | (1 << i)], g[s] + tmp);
        }
  memset(f, 0xc0, sizeof f);
  f[0][1] = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (!G[i][j]) G[i][j] = -0x3f3f3f3f;
  for (int i = 0; i < n; ++i)
    for (int s = 0; s < (1 << n); ++s)
      if (f[i][s] >= 0) {
        for (int j = 0; j < n; ++j)
          if (((~s >> j) & 1)) upd(f[j][s | (1 << j)], f[i][s] + G[i][j]);
        for (int cs = ((1 << n) - 1) ^ s, t = cs; t; t = (t - 1) & cs)
          upd(f[i][s | t], f[i][s] + g[t | (1 << i)]);
      }
  printf("%d\n", sum - f[n - 1][(1 << n) - 1]);
  return 0;
}
