#include <bits/stdc++.h>
using namespace std;
const int N = 15, inf = 1e9;
int w[N][N], n, m, prep[N][1 << N], dp[N][1 << N];
int cost(int s, int t) {
  int res = 0, mask = 0;
  for (int i = 0; i < n; ++i) mask += (1 << i) * ((s >> i) & 1);
  for (int i = 0; i < n; ++i) res += prep[i][mask] * ((t >> i) & 1);
  return res;
}
signed main() {
  memset(dp, 0x3f, sizeof(dp));
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c, --u, --v;
    w[u][v] = w[v][u] = c;
  }
  for (int i = 0; i < n; ++i) {
    for (int mask = 0; mask < (1 << n); ++mask) {
      for (int j = 0; j < n; ++j) {
        if (mask & (1 << j)) prep[i][mask] += w[i][j];
      }
    }
  }
  dp[0][1] = 0;
  for (int mask = 1; mask < (1 << n); mask += 2) {
    for (int i = 1; i < n; ++i) {
      if (!(mask & (1 << i))) {
        for (int j = 0; j < n; ++j) {
          if (mask & (1 << j) && w[j][i]) {
            dp[i][mask | (1 << i)] =
                min(dp[i][mask | (1 << i)],
                    dp[j][mask] + cost(mask ^ (1 << j), (1 << i)));
          }
        }
      }
    }
    int comp = (1 << n) - mask;
    for (int sub = comp; sub > 0; sub = (sub - 1) & comp) {
      for (int i = 1; i < n; ++i) {
        if (mask & (1 << i)) {
          dp[i][mask | sub] =
              min(dp[i][mask | sub], dp[i][mask] + cost(mask ^ (1 << i), sub));
        }
      }
    }
  }
  cout << dp[n - 1][(1 << n) - 1];
}
