#include <bits/stdc++.h>
using namespace std;
const int MAXN = 17, MAXS = 32775;
class solver {
 public:
  int n, m, N, g[MAXN][MAXN], val[MAXS], dp[MAXS][MAXN];
  vector<pair<int, int> > vv;
  vector<int> vc;
  inline void update(int &a, int b) {
    if (a < b) a = b;
  }
  int main() {
    memset(g, 0, sizeof(g));
    memset(dp, 0, sizeof(dp));
    memset(val, 0, sizeof(val));
    int i, j, k, r, rest, u, v, w, sum = 0;
    N = 1 << n;
    for (i = 1; i <= m; ++i) {
      u = vv[i - 1].first;
      v = vv[i - 1].second;
      w = vc[i - 1];
      g[u][v] = g[v][u] = w;
      sum += w;
    }
    memset(dp, -1, sizeof(dp));
    for (i = 1; i < N; ++i) {
      for (j = 0; j < n; ++j)
        if (i & (1 << j)) break;
      val[i] = val[i ^ (1 << j)];
      for (k = j + 1; k < n; ++k)
        if (i & (1 << k)) val[i] += g[j][k];
      if (j == 0) dp[i][0] = val[i];
    }
    for (i = 1; i < N; ++i)
      for (j = 0; j < n; ++j) {
        if ((v = dp[i][j]) < 0) continue;
        for (k = 0; k < n; ++k) {
          if (i & (1 << k)) continue;
          if (g[j][k] == 0) continue;
          update(dp[i ^ (1 << k)][k], v + g[j][k]);
          for (rest = r = (N - 1) ^ i ^ (1 << k); r; r = (r - 1) & rest)
            update(dp[i ^ r ^ (1 << k)][k], v + val[r ^ (1 << k)] + g[j][k]);
        }
      }
    return sum - dp[N - 1][n - 1];
    return 0;
  }
};
solver sol;
int n;
int m;
struct st {
  int a;
  int b;
  long long int c;
};
vector<st> road;
long long int cost[1 << 16];
long long int dp[1 << 16][16];
long long int lis[16][16];
long long int ddp[1 << 16];
long long int mt[1 << 16][16];
int main() {
  cin >> n >> m;
  sol.n = n;
  sol.m = m;
  if (n == 1) return 1;
  long long int S = 0;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    sol.vv.push_back(make_pair(a, b));
    sol.vc.push_back(c);
    road.push_back({a, b, c});
    S += c;
    if (lis[a][b]) return 1;
    lis[a][b] = max(lis[a][b], (long long int)c);
    lis[b][a] = max(lis[b][a], (long long int)c);
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) continue;
      for (int k = 0; k < n; k++) {
        if ((i >> k) & 1) {
          mt[i][j] = max(mt[i][j], lis[k][j]);
        }
      }
    }
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < road.size(); j++) {
      if ((i >> road[j].a) & 1) {
        if ((i >> road[j].b) & 1) {
          cost[i] += road[j].c;
        }
      }
    }
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = LLONG_MIN;
    }
  }
  dp[1][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (!(i >> j) & 1) {
        continue;
      }
      if (dp[i][j] != LLONG_MIN) {
        for (int k = 0; k < n; k++) {
          if ((i >> k) & 1) continue;
          if (lis[j][k]) {
            dp[i | (1 << k)][k] =
                max(dp[i | (1 << k)][k], dp[i][j] + lis[j][k]);
          }
        }
      }
    }
  }
  for (int i = 0; i < (1 << n); i++) {
    ddp[i] = dp[i][n - 1];
  }
  for (int i = 0; i < (1 << n); i++) {
    if (ddp[i] != LLONG_MIN) {
      if ((!(i >> 0) & 1) || (!(i >> (n - 1) & 1))) {
        return 1;
      }
      for (int j = i; j < (1 << n); j++, j |= i) {
        if (i == j) continue;
        int xr = (j ^ i);
        if (xr & i) return 1;
        if (xr == 0) return 1;
        long long int cosm = max(cost[1 | xr], cost[(1 << (n - 1)) | xr]);
        for (int ii = 0; ii < n; ii++) {
          if ((i >> ii) & 1) {
            cosm = max(cosm, mt[xr][ii] + cost[xr]);
          }
        }
        ddp[j] = max(ddp[j], ddp[i] + cosm);
      }
    }
  }
  int s = sol.main();
  if (s < S - ddp[(1 << n) - 1]) {
    return 1;
  }
  printf("%lld\n", S - ddp[(1 << n) - 1]);
  return 0;
}
