#include <bits/stdc++.h>
using namespace std;
int read() {
  int ans = 0;
  char ch = getchar();
  for (; (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  bool flag = 0;
  if (ch == '-') flag = 1, ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) ans = ans * 10 + ch - '0';
  if (flag) ans = -ans;
  return ans;
}
long long rell() {
  long long ans = 0;
  char ch = getchar();
  for (; (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  bool flag = 0;
  if (ch == '-') flag = 1, ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    ans = ans * 10ll + (long long)(ch - '0');
  if (flag) ans = -ans;
  return ans;
}
void writ(int n) {
  char ch[25];
  int m = 0;
  if (n < 0) putchar('-'), n = -n;
  if (n == 0) {
    putchar('0');
    return;
  }
  for (; n; n /= 10) ch[m++] = n % 10ll + '0';
  for (; m;) putchar(ch[--m]);
}
void wrll(long long n) {
  char ch[25];
  int m = 0;
  if (n < 0) putchar('-'), n = -n;
  if (n == 0) {
    putchar('0');
    return;
  }
  for (; n; n /= 10ll) ch[m++] = n % 10ll + '0';
  for (; m;) putchar(ch[--m]);
}
const int N = 16;
int g[N][N], sum[1 << N], dp[N][1 << N];
int main() {
  int n = read(), m = read(), gsum = 0;
  memset(g, 0, sizeof(g));
  for (int i = 0; i < m; i++) {
    int u = read() - 1, v = read() - 1;
    g[u][v] = g[v][u] = read();
    gsum += g[u][v];
  }
  sum[0] = 0;
  for (int i = 1; i < (1 << n); i++) {
    int j = 0;
    for (; !(i & (1 << j)); j++)
      ;
    sum[i] = sum[i - (1 << j)];
    for (int k = j + 1; k < n; k++)
      if (i & (1 << k)) {
        sum[i] += g[j][k];
      }
  }
  memset(dp, 192, sizeof(dp));
  dp[0][1] = 0;
  for (int i = 1; i < (1 << n); i++) {
    for (int j = 0; j < n; j++)
      if (i & (1 << j)) {
        int I = i - (1 << j);
        for (int k = (I - 1) & I; k; k = (k - 1) & I) {
          dp[j][i] = max(dp[j][i], dp[j][i - k] + sum[k + (1 << j)]);
        }
        for (int k = 0; k < n; k++)
          if (I & (1 << k) && g[j][k]) {
            dp[j][i] = max(dp[j][i], dp[k][I] + g[j][k]);
          }
      }
  }
  writ(gsum - dp[n - 1][(1 << n) - 1]);
  puts("");
  return 0;
}
