#include <bits/stdc++.h>
using namespace std;
const int MAXN = 17, MAXS = 32775;
struct stane {
  int a, b;
  int c;
};
int n, m, N, g[20][20], val[40010], dp[40010][20];
vector<pair<int, int> > vv;
vector<int> vc;
inline void update(int &a, int b) {
  if (a < b) a = b;
}
int solve() {
  memset(g, 0, sizeof g);
  memset(val, 0, sizeof val);
  int i, j, k, r, rest, u, v, w;
  int 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;
}
vector<stane> road;
int cost[1 << 16];
int dp2[1 << 16][16];
int lis[16][16];
int ddp[1 << 16];
int mt[1 << 16][16];
int main() {
  cin >> n >> m;
  if (n == 1) return 1;
  int second = 0;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    vv.push_back(make_pair(a, b));
    vc.push_back(c);
    road.push_back({a, b, c});
    second += c;
    if (lis[a][b]) return 1;
    lis[a][b] = max(lis[a][b], (int)c);
    lis[b][a] = max(lis[b][a], (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++) dp2[i][j] = LLONG_MIN;
  dp2[1][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (!(i >> j) & 1) continue;
      if (dp2[i][j] != LLONG_MIN)
        for (int k = 0; k < n; k++) {
          if ((i >> k) & 1) continue;
          if (lis[j][k])
            dp2[i | (1 << k)][k] =
                max((int)dp2[i | (1 << k)][k], dp2[i][j] + lis[j][k]);
        }
    }
  }
  for (int i = 0; i < (1 << n); i++) ddp[i] = dp2[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;
        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, cost[1 << (ii) | xr]);
        ddp[j] = max(ddp[j], ddp[i] + cosm);
      }
    }
  }
  cout << second - ddp[(1 << n) - 1] << endl;
  return 0;
}
