#include <bits/stdc++.h>
using namespace std;
int N, M;
int self[1 << 15];
int dp[1 << 15][15];
int gph[15][15];
int l2[1 << 15];
int sumc;
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a -= 1;
    b -= 1;
    gph[a][b] = gph[b][a] = c;
    sumc += c;
  }
  for (int i = 0; i < N; i++) {
    l2[1 << i] = i;
  }
  for (int mask = 1; mask < (1 << N); mask++) {
    int cost = 0;
    for (int u = 0; u < N; u++)
      if (((mask >> u) & 1) == 1) {
        for (int v = u + 1; v < N; v++)
          if (((mask >> v) & 1) == 1) cost += gph[u][v];
      }
    self[mask] = cost;
  }
  for (int mask = 1; mask < (1 << N); mask++) {
    for (int u = 0; u < N; u++) dp[mask][u] = -1e9;
  }
  dp[1][0] = 0;
  for (int mask = 3; mask < (1 << N); mask += 2) {
    dp[mask][0] = self[mask];
    for (int vmask_ = mask >> 1; vmask_ >= 0;
         vmask_ = (vmask_ - 1) & (mask >> 1)) {
      int vmask = (vmask_ << 1) | 1;
      assert((vmask & mask) == vmask);
      for (int u = 0; u < N; u++)
        if ((vmask >> u) & 1) {
          for (int v = 1; v < N; v++)
            if (((mask ^ vmask) >> v) & 1) {
              dp[mask][v] = max(dp[mask][v],
                                dp[vmask][u] + self[mask ^ vmask] + gph[u][v]);
            }
        }
      if (vmask == 1) {
        break;
      }
    }
  }
  printf("%d\n", sumc - dp[(1 << N) - 1][N - 1]);
  return 0;
}
