#include <bits/stdc++.h>
using namespace std;
int n, m;
int add[1 << 15];
int dp[1 << 15][15];
int i, j, k, p;
int x, y, z;
int mp[15][15];
int main() {
  cin >> n >> m;
  while (m--) {
    cin >> x >> y >> z;
    mp[x - 1][y - 1] = z;
    mp[y - 1][x - 1] = z;
  }
  for (i = 0; i < (1 << n); i++) {
    for (j = 0; j < n; j++) {
      if ((1 << j) & i) {
        for (k = j + 1; k < n; k++) {
          if ((1 << k) & i) {
            add[i] += mp[k][j];
          }
        }
      }
    }
  }
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  for (i = 1; i < (1 << n); i++) {
    for (j = 0; j < n; j++) {
      if ((1 << j) & i) {
        if (dp[i][j] != -1) {
          for (k = 0; k < n; k++) {
            if (!((1 << k) & i)) {
              if (mp[j][k]) {
                dp[i | (1 << k)][k] =
                    max(dp[i | (1 << k)][k], dp[i][j] + mp[j][k]);
              }
            }
          }
          int bj = ((((1 << n) - 1) ^ i) | (1 << j));
          for (k = bj;; k = ((k - 1) & bj)) {
            dp[i | k][j] = max(dp[i | k][j], dp[i][j] + add[k]);
            if (!k) break;
          }
        }
      }
    }
  }
  int ans = 0;
  for (i = 1; i < (1 << n); i++) ans = max(ans, dp[i][n - 1]);
  cout << add[(1 << n) - 1] - ans << endl;
  return 0;
}
