#include <bits/stdc++.h>
using namespace std;
int n, m, a[15][15], *b, i, j, k, x, y, z, val, tot, ret;
vector<int> f[(1 << 15) + 1];
inline void upd(int& a, int b) { a = a < b ? a : b; }
inline int trans(int s, int t) {
  ret = 0;
  while (s) {
    if (s & 1) ret = ret << 1 | (t & 1);
    s >>= 1, t >>= 1;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  while (m--)
    scanf("%d%d%d", &x, &y, &z), a[x - 1][y - 1] = a[y - 1][x - 1] = z;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (i != j && !a[i][j]) a[i][j] = 19260817;
  for (i = 0; i < (1 << n); i++)
    f[i] = vector<int>((1 << __builtin_popcount(i)) + 1, 0x3f3f3f3f);
  for (i = 0; i < (1 << n); i++) {
    for (j = i; j; j = (j - 1) & i) {
      y = trans(i, j);
      if (val = f[i][y]) {
        for (x = 0; x < n; x++)
          if (!(i & (1 << x))) {
            b = a[x], tot = 0;
            for (k = 0; k < n; k++)
              if ((i & (1 << k)) && (j & (1 << k))) tot += b[k];
            z = trans(i + (1 << x), j + (1 << x));
            upd(f[i + (1 << x)][z], val + tot);
          }
      }
    }
  }
  x = 0x3f3f3f3f;
  for (i = 0; i < (1 << n); i++) upd(x, f[(1 << n) - 1][i]);
  cout << x;
  return 0;
}
