#include <bits/stdc++.h>
using namespace std;
int dp[66666][17][17], n, m, mp[17][17], xx, yy, zz, k, sum;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> xx >> yy >> zz;
    xx--;
    yy--;
    mp[xx][yy] = zz;
    mp[yy][xx] = zz;
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) dp[i][j][k] = 1e9;
    }
    for (int j = 0; j < n; j++) dp[i][j][j] = 0;
  }
  for (int i = 1; i < (1 << n); i++) {
    for (int j = i; j; j = (j - 1) & i) {
      k = i ^ j;
      sum = 0;
      for (int x = 0; x < n; x++) {
        if (j & (1 << x)) {
          for (int y = 0; y < n; y++) {
            if (k & (1 << y)) sum += mp[x][y];
          }
        }
      }
      for (int x = 0; x < 1; x++) {
        if (j & (1 << x)) {
          for (int y = 0; y < n; y++) {
            if (k & (1 << y)) {
              for (int z = 0; z < n; z++) {
                if (j & (1 << z) && mp[y][z]) {
                  dp[i][x][y] = min(dp[i][x][y], dp[j][x][z] + sum - mp[y][z]);
                }
              }
            }
          }
        }
      }
    }
  }
  cout << dp[(1 << n) - 1][0][n - 1] << endl;
  return 0;
}
