#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 15;
int n, m;
int tb[N][N];
int sum[1 << N];
int tmp[1 << N][N], dp[1 << N][N];
void prt_bitmsk(int x) {
  for (int i = 0; i < n; i++) cout << !!(x & 1 << i);
}
int main() {
  cin >> n >> m;
  int tot = 0;
  while (m--) {
    int x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    tb[x][y] = tb[y][x] = z;
    tot += z;
  }
  for (int i = 0; i < 1 << n; i++) {
    for (int j = 0; j < n; j++)
      if (i & 1 << j)
        for (int k = 0; k < n; k++)
          if (i & 1 << k) sum[i] += tb[j][k];
    sum[i] >>= 1;
  }
  for (int i = 0; i < 1 << n; i++)
    for (int j = 0; j < n; j++) tmp[i][j] = -inf;
  for (int k = 1; k < n; k++)
    if (tb[0][k]) tmp[0][k] = max(tmp[0][k], tb[0][k]);
  int mx = 0;
  for (int i = 0; i < 1 << n; i++)
    if (i & 1 ^ 1)
      for (int j = 1; j < n; j++)
        if (i & 1 << j) {
          for (int k = i ^ 1 << j;; k = k - 1 & (i ^ 1 << j)) {
            dp[i][j] = max(dp[i][j], sum[k | 1 << j] + tmp[i ^ k ^ 1 << j][j]);
            if (!k) break;
          }
          if (j == n - 1) mx = max(mx, dp[i][j]);
          for (int k = 1; k < n; k++)
            if (!(i & 1 << k))
              if (tb[j][k]) tmp[i][k] = max(tmp[i][k], dp[i][j] + tb[j][k]);
        }
  cout << tot - mx;
  return 0;
}
