#include <bits/stdc++.h>
using namespace std;
const int INF = ~0u >> 2;
int n, m, sum[1 << 15], dp[1 << 15][15], G[15][15];
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
int cost(int x, int y) { return sum[x | y] - sum[x] - sum[y]; }
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    int x = read(), y = read(), z = read();
    x--;
    y--;
    G[x][y] = G[y][x] = z;
  }
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j)
      if (i & (1 << j)) {
        for (int k = j + 1; k < n; ++k)
          if (i & (1 << k)) sum[i] += G[j][k];
      }
  }
  for (int i = 1; i < (1 << n); ++i)
    for (int j = 0; j < n; ++j) dp[i][j] = INF;
  dp[1][0] = 0;
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j)
      if (dp[i][j] != INF) {
        for (int k = 0; k < n; ++k)
          if (!(i & (1 << k)) && G[j][k])
            dp[i | (1 << k)][k] =
                min(dp[i | (1 << k)][j], dp[i][j] + cost(i ^ (1 << j), 1 << k));
        for (int k = ((1 << n) - 1) & (~i); k > 0; k = (k - 1) & (~i))
          dp[i | k][j] = min(dp[i | k][j], dp[i][j] + cost(i ^ (1 << j), k));
      }
  }
  printf("%d", dp[(1 << n) - 1][n - 1]);
  return 0;
}
