#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void wrote(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) wrote(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(int x) {
  wrote(x);
  puts("");
}
const int sz = (1 << 15), N = 16;
int n, m, f[sz][N], g[sz][N], mp[N][N];
int main() {
  n = read();
  m = read();
  while (m--) {
    int x = read() - 1, y = read() - 1, w = read();
    mp[x][y] = mp[y][x] = w;
  }
  int all = (1 << n) - 1;
  for (int S = 0; S <= all; ++S)
    for (int i = 0; i <= n - 1; ++i)
      if ((S >> i) & 1)
        for (int j = 0; j <= n - 1; ++j) f[S][j] += mp[i][j];
  memset(g, 60, sizeof g);
  for (int S = 1; S <= all; ++S) g[S][0] = 0;
  for (int S = 1; S <= all; ++S)
    for (int i = 0; i <= n - 1; ++i)
      if ((S >> i) & 1)
        for (int T = all ^ S; T; T = (T - 1) & (all ^ S)) {
          int ans = 0;
          for (int j = 0; j <= n - 1; ++j)
            if ((T >> j) & 1) ans += f[S][j];
          for (int j = 0; j <= n - 1; ++j)
            if (((T >> j) & 1) && (mp[i][j]))
              g[S | T][j] = min(g[S | T][j], g[S][i] + ans - mp[i][j]);
        }
  int answ = 1e9 + 7;
  for (int S = 1; S <= all; ++S) {
    int T = S ^ all, ans = 0;
    for (int i = 0; i <= n - 1; ++i)
      if ((T >> i) & 1) ans += f[S][i];
    answ = min(answ, ans + g[S][n - 1]);
  }
  writeln(answ);
}
