#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAX = 16;
int dp[1 << MAX][MAX];
int costs[1 << MAX];
int G[MAX][MAX];
int main() {
  int N, M, a, b, c, all_costs = 0;
  cin >> N >> M;
  memset(G, -1, sizeof(G));
  for (int i = 0; i < M; i++) {
    cin >> a >> b >> c;
    a--, b--;
    G[a][b] = G[b][a] = c;
    all_costs += c;
  }
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++) {
      for (int k = j + 1; k < N; k++) {
        if (!((i >> j) & 1)) continue;
        if (!((i >> k) & 1)) continue;
        costs[i] += G[j][k];
      }
    }
  }
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++) {
      dp[i][j] = -INF;
    }
  }
  for (int i = 0; i < (1 << N); i++) {
    if (i & 1) {
      dp[i][0] = costs[i];
    }
  }
  int mask = ((1 << N) - 1);
  for (int S = 0; S < (1 << N); S++) {
    for (int i = 0; i < N; i++) {
      if (dp[S][i] == -INF) continue;
      int sup = (~S) & mask;
      int sub = sup;
      do {
        for (int j = 0; j < N; j++) {
          if (!((sub >> j) & 1)) continue;
          if (G[i][j] == -1) continue;
          dp[S | sub][j] = max(dp[S | sub][j], dp[S][i] + G[i][j] + costs[sub]);
        }
        sub = (sub - 1) & sup;
      } while (sub != sup);
    }
  }
  cout << all_costs - dp[(1 << N) - 1][N - 1] << endl;
}
