#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void ckmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void ckmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
const int oo = 1000000000;
int n, m;
int f[1 << 15][16][16];
int g[16][16];
int main() {
  while (cin >> n >> m) {
    memset(g, 255, sizeof(g));
    for (int i = 0; i < (m); ++i) {
      int x, y, z;
      cin >> x >> y >> z;
      --x;
      --y;
      g[x][y] = g[y][x] = z;
    }
    for (int set = 0; set < ((1 << (n))); ++set) {
      for (int x = 0; x < (n); ++x)
        for (int y = 0; y < (n); ++y) f[set][x][y] = oo;
      for (int x = 0; x < (n); ++x) f[set][x][x] = 0;
      for (int set1 = set - 1; set1 > 0; set1 = ((set1 - 1) & set)) {
        if (!(((set1) & (1 << (0))) != 0)) continue;
        int set2 = (set ^ set1);
        int base = 0;
        for (int x = 0; x < (n); ++x)
          if ((((set1) & (1 << (x))) != 0))
            for (int y = 0; y < (n); ++y)
              if ((((set2) & (1 << (y))) != 0) && g[x][y] >= 0) base += g[x][y];
        for (int x = 0; x < (n); ++x)
          if ((((set1) & (1 << (x))) != 0))
            for (int y = 0; y < (n); ++y)
              if ((((set1) & (1 << (y))) != 0))
                for (int z = 0; z < (n); ++z)
                  if ((((set2) & (1 << (z))) != 0) && g[y][z] >= 0) {
                    ckmin(f[set][x][z], base + f[set1][x][y] - g[y][z]);
                  }
      }
    }
    printf("%d\n", f[(1 << (n)) - 1][0][n - 1]);
    return 0;
  }
}
