#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[15][15];
int cost[1 << 15];
int mx[15][1 << 15];
unordered_map<int, int> dp[1 << 15];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    c[u][v] = c[v][u] = w;
  }
  for (int s = 0; s < (1 << n); s++) {
    for (int i = 0; i < n; i++) {
      if ((s >> i & 1) == 0) continue;
      for (int j = i + 1; j < n; j++) {
        if ((s >> j & 1) == 0) continue;
        cost[s] += c[i][j];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int s = 0; s < (1 << n); s++) {
      for (int j = 0; j < n; j++) {
        if (s >> j & 1) mx[i][s] = max(mx[i][s], c[i][j]);
      }
    }
  }
  dp[1][1] = 0;
  for (int s = 0; s < (1 << n); s++) {
    for (int t = s; t; t = (t - 1) & s) {
      if (dp[s].count(t) == 0) continue;
      for (int i = 0; i < n; i++) {
        if (s >> i & 1) continue;
        if (mx[i][t])
          dp[s | (1 << i)][1 << i] =
              max(dp[s | 1 << i][1 << i], dp[s][t] + mx[i][t]);
        dp[s | 1 << i][t | 1 << i] = max(dp[s | 1 << i][t | 1 << i],
                                         dp[s][t] + cost[t | 1 << i] - cost[t]);
      }
    }
  }
  int ans = 0;
  for (int i = 1; i < (1 << n) - 1; i++) ans = max(ans, dp[(1 << n) - 1][i]);
  printf("%d\n", cost[(1 << n) - 1] - ans);
  return 0;
}
