#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int MAXN = 15;
const int MAXP = (1 << MAXN);
int N, M;
int edge[MAXN][MAXN];
int cscore[MAXP];
int dp[MAXN][MAXP];
vector<int> Mask[MAXP];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> N >> M;
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++) {
      if (i & (1 << j)) Mask[i].push_back(j);
    }
  }
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    edge[a][b] = edge[b][a] = c;
  }
  vector<int> v;
  for (int i = 1; i < (1 << N); i++) {
    v.clear();
    for (int j = 0; j < N; j++)
      if (i & (1 << j)) {
        v.push_back(j);
      }
    cscore[i] = cscore[i ^ (1 << (v[0] - 1))];
    for (int j = 1; j < v.size(); j++) {
      cscore[i] += edge[v[0]][v[j]];
    }
  }
  for (int i = 0; i < MAXN; i++)
    for (int j = 0; j < MAXP; j++) dp[i][j] = -1e9;
  for (int i = 1; i < (1 << N); i += 2) dp[0][i] = cscore[i];
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++)
      if (i & (1 << j)) {
        if (dp[j][i] < 0) continue;
        int mask = (1 << N) - 1 - i;
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
          for (auto k : Mask[sub]) {
            if (edge[j][k])
              dp[k][i + sub] =
                  max(dp[k][i + sub], dp[j][i] + cscore[sub] + edge[j][k]);
          }
        }
      }
  }
  cout << cscore[(1 << N) - 1] - dp[N - 1][(1 << N) - 1] << "\n";
}
