#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long e[15][15];
long long dp2[1 << 15];
long long dfs2(long long b) {
  if (~dp2[b]) return dp2[b];
  if (b == 0) return dp2[0] = 0;
  long long res = 0;
  for (long long i = 0; i < n; i++) {
    if ((b >> i) & 1) {
      long long nb = b ^ (1 << i);
      long long tmp = 0;
      for (long long j = 0; j < n; j++) {
        if (e[i][j] < 0) continue;
        if ((b >> j) & 1) tmp += e[i][j];
      }
      res = max(res, dfs2(nb) + tmp);
    }
  }
  return dp2[b] = res;
}
long long dp[15][1 << 15];
long long dfs(long long v, long long b);
long long rec(long long v, long long b, long long k, long long p) {
  long long res = 0;
  for (long long i = p; i < n - 1; i++) {
    if (((b >> i) & 1) || ((k >> i) & 1)) continue;
    res = max(res, rec(v, b, k | (1 << i), i + 1));
  }
  for (long long i = 0; i < n; i++) {
    if (((b >> i) & 1) || ((k >> i) & 1)) continue;
    if (e[v][i] < 0) continue;
    res = max(res, dfs(i, b | k) + e[v][i] + dp2[k]);
  }
  return res;
}
long long dfs(long long v, long long b) {
  if (~dp[v][b]) return dp[v][b];
  if (v == n - 1) {
    long long nb = (~b) & ((1 << n) - 1);
    return dp[v][b] = dp2[nb];
  }
  return dp[v][b] = rec(v, b, (1 << v), 0);
}
signed main() {
  cin >> n >> m;
  memset(e, -1, sizeof(e));
  long long sum = 0;
  for (long long i = 0; i < m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    e[a][b] = e[b][a] = c;
    sum += c;
  }
  memset(dp2, -1, sizeof(dp2));
  dfs2((1 << n) - 1);
  assert(dp2[(1 << n) - 1] == sum);
  memset(dp, -1, sizeof(dp));
  cout << sum - dfs(0, 0) << endl;
  return 0;
}
