#include <bits/stdc++.h>
using namespace std;
int dp[(1 << 15) + 10][18];
int su[(1 << 15)];
int co[20][20];
int main() {
  int n, m, sum = 0, a, b, c;
  memset(co, 0, sizeof(co));
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    a--;
    b--;
    co[a][b] = co[b][a] = c;
    sum += c;
  }
  memset(su, 0, sizeof(su));
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
      for (int k = j + 1; k < n; k++) {
        if ((i & (1 << j)) && (i & (1 << k))) su[i] += co[j][k];
      }
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j < n; j++) {
      if (dp[i][j] < 0) continue;
      for (int k = 0; k < n; k++) {
        if (i & (1 << k) || co[j][k] < 1) continue;
        dp[i + (1 << k)][k] = max(dp[i + (1 << k)][k], dp[i][j] + co[j][k]);
      }
      int x = (1 << n) - 1 - j;
      for (int y = x; y > 0; y = ((y - 1) & x)) {
        dp[i + y][j] = max(dp[i + y][j], dp[i][j] + su[y + (1 << j)]);
      }
    }
  cout << sum - dp[(1 << n) - 1][n - 1] << endl;
}
