#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 200000;
int a[N][N], f[M][N], g[M][N], n, m, x, y, z;
inline void read(int &x) {
  char c = getchar();
  x = 0;
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
}
inline int work(int x, int y) {
  int sum = 0;
  for (int i = 0; i < n; ++i)
    if ((x >> i) & 1) sum += f[y][i];
  return sum;
}
int main() {
  read(n);
  read(m);
  memset(g, 0x3f, sizeof(g));
  for (int i = 1; i <= m; ++i) {
    read(x);
    read(y);
    read(z);
    --x;
    --y;
    a[x][y] = a[y][x] = z;
  }
  for (int i = 0; i < (1 << n); ++i)
    for (int j = 0; j < n; ++j)
      for (int k = 0; k < n; ++k)
        if ((i >> k) & 1) f[i][j] += a[j][k];
  g[1][0] = 0;
  for (int i = 0; i < (1 << n); ++i)
    for (int j = 0; j < n; ++j)
      if ((i >> j) & 1) {
        for (int k = 0; k < n; ++k)
          if (a[j][k] && (!(i >> k) & 1))
            g[i | (1 << k)][k] =
                min(g[i | (1 << k)][k], g[i][j] + work(i, 1 << k) - a[j][k]);
        int u = (1 << n) - 1 - i;
        for (int k = u; k; k = (k - 1) & u)
          g[i | k][j] = min(g[i | k][j], g[i][j] + work(i ^ (1 << j), k));
      }
  printf("%d", g[(1 << n) - 1][n - 1]);
  return 0;
}
