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