#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, l, mp[25][25], all[1 << 16], dp[1 << 16][25], x, y, z, sum,
    ans;
int main() {
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    cin >> x >> y >> z;
    x--;
    y--;
    sum += z;
    mp[x][y] = mp[y][x] = z;
  }
  for (i = 0; i < (1 << n); i++) {
    for (j = 0; j < n; j++)
      if ((i >> j) & 1) {
        for (k = j + 1; k < n; k++)
          if ((i >> k) & 1) {
            all[i] += mp[j][k];
          }
      }
  }
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  for (i = 1; i < (1 << n); i++) {
    for (j = 0; j < n; j++)
      if ((i >> j) & 1)
        if (dp[i][j] != -1) {
          for (k = ((((1 << n) - 1) ^ i) | (1 << j)); k;
               k = ((k - 1) & ((((1 << n) - 1) ^ i) | (1 << j)))) {
            dp[i | k][j] = max(dp[i | k][j], dp[i][j] + all[k]);
          }
          for (k = 0; k < n; k++)
            if (!((i >> k) & 1))
              if (mp[j][k]) {
                dp[i | (1 << k)][k] =
                    max(dp[i | (1 << k)][k], dp[i][j] + mp[j][k]);
              }
        }
    if ((i >> (n - 1)) & 1) ans = max(ans, dp[i][n - 1]);
    if (ans > 1234567) {
      system("pause");
    }
  }
  cout << sum - ans << endl;
  return 0;
}
