#include <bits/stdc++.h>
using namespace std;
int N, M;
int G[15][15];
int cost[1 << 15];
int dp[15][1 << 15];
int main() {
  cin >> N >> M;
  int u, v, w;
  int tot = 0;
  for (int i = 1; i <= M; i++) {
    cin >> u >> v >> w;
    --u;
    --v;
    G[u][v] = G[v][u] = w;
    tot += w;
  }
  for (int s = 1; s < (1 << N); s++) {
    for (u = 0; u < N; u++) {
      if (((s >> u) & 1) == 0) continue;
      for (int v = u + 1; v < N; v++) {
        if (((s >> v) & 1) == 0) continue;
        cost[s] += G[u][v];
      }
    }
  }
  int ans = 0;
  memset(dp, 0xf3, sizeof(dp));
  dp[0][1] = 0;
  int U = (1 << N) - 1;
  for (u = 0; u < N; u++) {
    for (int s = 1; s < (1 << N); s++) {
      if (((s >> u) & 1) == 0) continue;
      if (u == N - 1) ans = max(ans, dp[N - 1][s]);
      for (v = 0; v < N; v++) {
        if (((s >> v) & 1) == 0 && G[u][v]) {
          dp[v][s | (1 << v)] = max(dp[v][s | (1 << v)], dp[u][s] + G[u][v]);
        }
      }
      int s1 = (U ^ s) | (1 << u);
      for (int s2 = s1; s2 > 0; s2 = (s2 - 1) & s1) {
        dp[u][s | s2] = max(dp[u][s | s2], dp[u][s] + cost[s2]);
      }
    }
  }
  cout << tot - ans << endl;
  return 0;
}
