#include <bits/stdc++.h>
using namespace std;
int V, E;
int i, u, v, w;
int G[20][20];
int f[65634][20];
int in[65634], out[20][65634], ans;
void up(int &x, const int y) { x < y ? x = y : 0; }
int main() {
  scanf("%d%d", &V, &E);
  for (i = 0; i < E; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    --u;
    --v;
    G[u][v] = G[v][u] = w;
    ans += w;
  }
  for (i = 0; i < 1 << V; ++i)
    for (u = 0; u < V; ++u)
      if (i >> u & 1)
        for (v = u + 1; v < V; ++v)
          if (i >> v & 1) in[i] += G[u][v];
  for (i = 0; i < 1 << V; ++i)
    for (u = 0; u < V; ++u)
      if (!(i >> u & 1))
        for (v = 0; v < V; ++v)
          if (i >> v & 1) out[u][i] += G[u][v];
  memset(f, 128, sizeof f);
  f[1][0] = 0;
  for (i = 1; i < 1 << V; ++i)
    for (u = 0; u < V; ++u)
      if ((i >> u & 1) && f[i][u] >= 0) {
        for (v = 0; v < V; ++v)
          if (!(i >> v & 1) && G[u][v]) up(f[i | 1 << v][v], f[i][u] + G[u][v]);
        v = ~(-1 << V | i);
        for (; v; v = v - 1 & ~i) up(f[i | v][u], f[i][u] + out[u][v] + in[v]);
      }
  printf("%d\n", ans -= f[(1 << V) - 1][V - 1]);
  return 0;
}
