#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15;
int cs[1 << MAX_N];
int con[MAX_N][1 << MAX_N];
int dp[1 << MAX_N][MAX_N];
int d[MAX_N][MAX_N];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int sm = 0;
  for (int i = 0; i < (int)(m); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    sm += c;
    d[a - 1][b - 1] = d[b - 1][a - 1] = c;
  }
  for (int i = 0; i < (int)((1 << n)); ++i) {
    for (int j = 0; j < (int)(n); ++j) {
      if (!(i >> j & 1)) {
        int res = cs[i];
        for (int k = 0; k < (int)(n); ++k) {
          if (i >> k & 1) {
            res += d[j][k];
          }
        }
        cs[i ^ (1 << j)] = max(cs[i ^ (1 << j)], res);
      }
    }
  }
  for (int i = 0; i < (int)(n); ++i) {
    for (int j = 0; j < (int)((1 << n)); ++j) {
      if (j >> i & 1) continue;
      con[i][j] = cs[j];
      for (int k = 0; k < (int)(n); ++k) {
        if (j >> k & 1) {
          con[i][j] += d[i][k];
        }
      }
    }
  }
  for (int k = (((1 << n) - 1) ^ 1);; k = (k - 1) & (((1 << n) - 1) ^ 1)) {
    int st = (1 ^ k);
    for (int l = 0; l < (int)(n); ++l) {
      if (!(st >> l & 1)) {
        dp[st ^ (1 << l)][l] =
            max(dp[st ^ (1 << l)][l], dp[0][0] + con[0][k] + d[0][l]);
      }
    }
    if (k == 0) break;
  }
  for (int i = (int)(3); i < (int)(1 << n); ++i) {
    for (int j = 0; j < (int)(n); ++j) {
      if (dp[i][j] == 0) continue;
      for (int k = (((1 << n) - 1) ^ i);; k = (k - 1) & (((1 << n) - 1) ^ i)) {
        int st = (i ^ k);
        for (int l = 0; l < (int)(n); ++l) {
          if (!(st >> l & 1)) {
            dp[st ^ (1 << l)][l] =
                max(dp[st ^ (1 << l)][l], dp[i][j] + con[j][k] + d[j][l]);
          }
        }
        if (k == 0) break;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < (int)((1 << n)); ++i) {
    if (dp[i][n - 1] == 0) continue;
    ans = max(ans, dp[i][n - 1] + con[n - 1][((1 << n) - 1) ^ i]);
  }
  cout << sm - ans << "\n";
  return 0;
}
