#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long xx = 0, flagg = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    flagg = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    xx = xx * 10 + ch - '0';
    ch = getchar();
  }
  return xx * flagg;
}
void pus(long long xx, long long flagg) {
  if (xx < 0) {
    putchar('-');
    xx = -xx;
  }
  if (xx >= 10) pus(xx / 10, 0);
  putchar(xx % 10 + '0');
  if (flagg == 1) putchar(' ');
  if (flagg == 2) putchar('\n');
  return;
}
int n, m, i, j, k, l, vis[20][20], a[100005], f[100005][20], x, y, z, ans,
    top[100005], b[100005][20];
int maxx(int u, int v) { return u > v ? u : v; }
int main() {
  n = read();
  m = read();
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) vis[i][j] = -1000000000;
  for (i = 1; i <= m; i++) {
    x = read() - 1;
    y = read() - 1;
    z = read();
    vis[x][y] = z;
    vis[y][x] = z;
    ans += z;
  }
  for (i = 0; i < (1 << n); i++)
    for (j = 0; j < n; j++)
      if ((1 << j) & i) {
        a[i] = a[i ^ (1 << j)];
        for (k = j; k < n; k++) {
          if (((1 << k) & i) && vis[j][k] > 0) a[i] += vis[j][k];
          if ((1 << k) & i) {
            top[i]++;
            b[i][top[i]] = k;
          }
        }
        break;
      }
  for (i = 0; i < (1 << n); i++)
    for (j = 0; j < n; j++) f[i][j] = -1000000000;
  f[1][0] = 0;
  for (i = 1; i < (1 << n); i += 2)
    for (j = 0; j < n; j++)
      if ((i & (1 << j)) && (i == (1 << n) - 1 || (i & (1 << n - 1)) == 0))
        for (k = (i - 1) & i; k >= 1; k = (k - 1) & i)
          if ((k & (1 << j)) == 0)
            for (l = 1; l <= top[k]; l++)
              if (k & (1 << b[k][l]))
                f[i][j] =
                    maxx(f[i][j], f[k][b[k][l]] + a[i ^ k] + vis[j][b[k][l]]);
  pus(ans - f[(1 << n) - 1][n - 1], 2);
  return 0;
}
