#include <bits/stdc++.h>
using namespace std;
const int Max_N = 15, Max_S = 1 << 15;
int N, M, Sum = 0, A[Max_N + 5][Max_N + 5] = {}, f[Max_S + 5][Max_N + 5] = {},
          P[Max_S + 5] = {};
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    Sum += v;
    A[x][y] = A[y][x] = v;
  }
  for (int i = 0; i < 1 << N; i++) {
    for (int j = 1; j <= N; j++)
      if ((1 << (j - 1)) & i) {
        for (int k = j + 1; k <= N; k++)
          if ((1 << (k - 1)) & i) P[i] += A[j][k];
      }
  }
  memset(f, -10, sizeof(f));
  f[1][1] = 0;
  for (int i = 0; i < 1 << N; i++) {
    for (int j = 2; j <= N; j++) {
      if ((1 << (j - 1)) & i)
        for (int k = 1; k <= N; k++)
          if (((1 << (k - 1)) & i) && k != j && A[j][k] > 0)
            f[i][j] = max(f[i][j], f[i ^ (1 << (j - 1))][k] + A[j][k]);
      for (int k = i; k; k = (k - 1) & i)
        if (k & (1 << (j - 1)))
          f[i][j] = max(f[i][j], f[(i ^ k) | (1 << (j - 1))][j] + P[k]);
    }
  }
  printf("%d\n", Sum - f[(1 << N) - 1][N]);
  return 0;
}
