#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000000LL;
const int MAX = 15;
int N, M;
int c[MAX][MAX];
int cc[1 << MAX];
int ce[MAX][1 << MAX];
int f[MAX][1 << MAX];
int g[MAX][1 << MAX];
bool got(int S, int i) { return (S >> i) & 1; }
int main(void) {
  scanf("%d%d", &N, &M);
  int tot = 0;
  for (int i = (0); i < (M); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    scanf("%d", &c[a][b]);
    c[b][a] = c[a][b];
    tot += c[a][b];
  }
  for (int i = (0); i < (N); ++i)
    for (int j = (0); j < (N); ++j)
      for (int S = (0); S < (1 << N); ++S) {
        if (!got(S, j) || got(S, i)) continue;
        ce[i][S] += c[i][j];
      }
  for (int S = (0); S < ((1 << N)); ++S)
    for (int j = (0); j < (N); ++j)
      if (!got(S, j)) cc[S | (1 << j)] = cc[S] + ce[j][S];
  for (int S = (0); S < (1 << N); ++S) {
    for (int i = (0); i < (N); ++i) {
      if (!got(S, i)) continue;
      int s = S ^ (1 << i);
      if (got(s, N - 1)) s ^= (1 << (N - 1));
      for (int z = s;; z = (z - 1) & s) {
        int Z = z ^ (1 << i);
        f[i][S] = max(f[i][S], g[i][S ^ Z] + cc[z] + ce[i][z]);
        if (z == 0) break;
      }
    }
    for (int i = (0); i < (N); ++i)
      if (!got(S, i))
        for (int j = (0); j < (N); ++j)
          if (got(S, j) && c[i][j]) g[i][S] = max(g[i][S], f[j][S] + c[i][j]);
  }
  printf("%d\n", tot - f[0][(1 << N) - 1]);
  return 0;
}
