#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
long long f[20][(1 << 15) + 5], n, m, sum, s[(1 << 15) + 5], mp[20][20];
signed main() {
  n = read(), m = read();
  for (long long i = 1, x, y, z; i <= m; x = read(), y = read(), z = read(),
                 x--, y--, mp[x][y] = mp[y][x] = z, sum += z, i++)
    ;
  for (long long S = 1; S < 1 << n; S++)
    for (long long i = 0; i < n; i++)
      if ((S >> i) & 1)
        for (long long j = i + 1; j < n; j++)
          if ((S >> j) & 1) s[S] += mp[i][j];
  memset(f, -1e9, sizeof(f));
  f[0][1] = 0;
  for (long long S = 1; S < 1 << n; S += 2)
    for (long long t = 0; t < n; t++)
      if ((S >> t) & 1) {
        for (long long i = 0; i < n; i++)
          if ((!(S >> i) & 1) && mp[t][i])
            f[i][S | (1 << i)] = max(f[i][S | (1 << i)], f[t][S] + mp[t][i]);
        long long SS = ((1 << n) - 1) ^ S;
        for (long long S1 = SS; S1; S1 = (S1 - 1) & SS)
          f[t][S | S1] = max(f[t][S | S1], f[t][S] + s[S1 | (1 << t)]);
      }
  cout << sum - f[n - 1][(1 << n) - 1];
}
