#include <bits/stdc++.h>
const int N = 200005;
long long r[20][N], f[20][N], sum[N], g[N];
long long v[20][20];
int read() {
  int x = 0, v = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; v = (ch == '-') ? (-1) : v, ch = getchar())
    ;
  for (; ch <= '9' && ch >= '0'; x = x * 10 + ch - '0', ch = getchar())
    ;
  return x * v;
}
void upd(long long &x, long long v) { (x < v) ? (x = v) : 0; }
int main(void) {
  int n = read(), m = read();
  long long prt = 0;
  for (int i = 1; i <= m; ++i) {
    int x = read() - 1, y = read() - 1;
    v[x][y] = v[y][x] = read(), prt += v[x][y];
    r[x][1 << y] = v[x][y];
    r[y][1 << x] = v[x][y];
  }
  for (int i = 0; i <= n - 1; ++i) {
    for (int S = 0; S < (1 << n); ++S) {
      r[i][S] = r[i][S - (S & -S)] + r[i][(S & -S)];
    }
  }
  for (int S = 0; S < (1 << n); ++S) {
    sum[S] = sum[S - (S & -S)] + r[((int)log2((S & -S)))][S - (S & -S)];
  }
  memset(f, -63, sizeof(f));
  f[0][1] = 0;
  long long ans = 0;
  for (int i = 0; i <= n - 1; ++i) {
    for (int S = (1 << n) - 1; S; --S) {
      if (!((S >> i)) & 1) continue;
      if (!(S & 1)) continue;
      for (int T = S; T; T = (T - 1) & S) {
        if (T >> i & 1) upd(f[i][S], f[i][S - T + (1 << i)] + sum[T]);
      }
      for (int j = 0; j <= n - 1; ++j)
        if (!(S >> j & 1) && v[i][j]) {
          upd(f[j][S + (1 << j)], f[i][S] + v[i][j]);
        }
    }
  }
  for (int S = 0; S < (1 << n); ++S)
    if ((S & 1) && (S >> (n - 1) & 1)) upd(ans, f[n - 1][S]);
  printf("%lld\n", prt - ans);
  return 0;
}
