#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> P) {
  out << '(' << P.first << ',' << P.second << ')';
  return out;
}
const int maxn = 15;
const int INF = 0x3f3f3f3f;
int es[1 << maxn];
int adj[maxn][maxn];
int dp[maxn][1 << maxn];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  long long tt = 0;
  for (int i = 0; i < ((int)m); i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--;
    v--;
    adj[u][v] = adj[v][u] = d;
    tt += d;
  }
  for (int i = 1; i < (1 << n); i++) {
    int tmp = 31 - __builtin_clz(i & -i);
    es[i] = es[i ^ (1 << tmp)];
    for (int j = tmp + 1; j < n; j++)
      if (i & (1 << j)) {
        es[i] += adj[tmp][j];
      }
  }
  for (int i = 0; i < ((int)n); i++)
    for (int j = 0; j < ((int)1 << n); j++) dp[i][j] = -INF;
  for (int mask = 0; mask < ((int)1 << n); mask++)
    for (int i = 0; i < n; i++)
      if (mask & (1 << i)) {
        if (i == 0)
          dp[i][mask] = es[mask];
        else {
          int pre = mask ^ (1 << i);
          for (int sub = pre; sub > 0; sub = (sub - 1) & pre) {
            for (int j = 0; j < ((int)n); j++)
              if (sub & (1 << j)) {
                if (adj[j][i])
                  dp[i][mask] =
                      max(dp[i][mask], dp[j][sub] + es[sub ^ mask] + adj[j][i]);
              }
          }
        }
      }
  cout << tt - dp[n - 1][(1 << n) - 1] << '\n';
  return 0;
}
