#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z, a[20][20], kk, f[20][40000], p[40000], sum;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
signed main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y >> z;
    if (x > y) swap(x, y);
    a[x][y] += z;
    sum += z;
  }
  kk = 1 << n;
  for (int l = 1; l < kk; l++)
    for (int i = 1; i <= n; i++)
      if (l & (1 << (i - 1)))
        for (int j = 1; j <= n; j++)
          if (l & (1 << (j - 1))) p[l] += a[i][j];
  memset(f, 200, sizeof(f));
  for (int i = 1; i < kk; i++)
    if (i & 1) f[1][i] = p[i];
  for (int i = 1; i < kk; i++)
    for (int x1 = 1; x1 <= n; x1++)
      if (i & (1 << (x1 - 1))) {
        int P = (kk - 1) ^ i;
        for (int x2 = 1; x2 <= n; x2++)
          if (a[min(x1, x2)][max(x1, x2)])
            for (int j = P; j; j = (j - 1) & P)
              if (j & (1 << (x2 - 1)))
                f[x2][i | j] =
                    max(f[x2][i | j],
                        f[x1][i] + a[min(x1, x2)][max(x1, x2)] + p[j]);
      }
  cout << sum - f[n][kk - 1] << endl;
}
