#include <bits/stdc++.h>
using namespace std;
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;
  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--;
    road.push_back({a, b, c});
    S += c;
    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);
        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);
      }
    }
  }
  printf("%lld\n", S - ddp[(1 << n) - 1]);
  return 0;
}
