#include <bits/stdc++.h>
using namespace std;
int n, m, mp[16][16], x, y, z, mmh[1 << 15][15], o[1 << 15][15];
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
inline int work(int a, int b) {
  int mmh = 0;
  for (int i = 0; i < n; i++)
    if ((a >> i) & 1) mmh += o[b][i];
  return mmh;
}
int main() {
  n = read();
  m = read();
  memset(mp, 0, sizeof(mp));
  memset(mmh, 63, sizeof(mmh));
  while (m--) {
    x = read();
    y = read();
    z = read();
    x--;
    y--;
    mp[x][y] = mp[y][x] = z;
  }
  for (int i = 0; i <= (1 << n) - 1; i++)
    for (int j = 0; j <= n - 1; j++) {
      o[i][j] = 0;
      for (int k = 0; k <= n - 1; k++)
        if ((i >> k) & 1) o[i][j] += mp[j][k];
    }
  mmh[1][0] = 0;
  for (int i = 0; i <= (1 << n) - 1; i++)
    for (int j = 0; j <= n - 1; j++)
      if ((i >> j) & 1) {
        for (int k = 0; k <= n - 1; k++)
          if (mp[j][k])
            if (!((i >> k) & 1))
              mmh[i | (1 << k)][k] = min(
                  mmh[i | (1 << k)][k], mmh[i][j] + work(i, 1 << k) - mp[j][k]);
        int u = (1 << n) - 1 - i;
        for (int p = u; p; p = (p - 1) & u)
          mmh[i | p][j] = min(mmh[i | p][j], mmh[i][j] + work(i ^ (1 << j), p));
      }
  printf("%d\n", mmh[(1 << n) - 1][n - 1]);
}
