#include <bits/stdc++.h>
using namespace std;
const int N = 17;
int n, m, a[N][N], f[1 << N][N], sum[1 << N];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, z;
    cin >> u >> v >> z;
    u--;
    v--;
    a[u][v] = a[v][u] = z;
  }
  for (int i = 1; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
      if (i & (1 << j))
        for (int k = j + 1; k < n; k++)
          if (i & (1 << k)) sum[i] += a[j][k];
  memset(f, 0xcf, sizeof(f));
  for (int i = 1; i < (1 << n); i++)
    if (i & 1) f[i][1] = sum[i];
  for (int i = 1; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
      if (i & (1 << j))
        for (int k = (i - 1) & i; k > 0; k = (k - 1) & i)
          if ((k & (1 << j)) == 0)
            for (int l = 0; l < n; l++)
              if ((k & (1 << l)) > 0 && a[j][l] > 0)
                f[i][j] = max(f[i][j], f[k][l] + a[j][l] + sum[i ^ k]);
  cout << sum[(1 << n) - 1] - f[(1 << n) - 1][n - 1] << endl;
  return 0;
}
