#include <bits/stdc++.h>
using namespace std;
int GLL(long long& x) { return scanf("%lld", &x); }
int GI(int& x) { return scanf("%d", &x); }
const int MAXN = 16;
long long cost[MAXN][MAXN], dp[MAXN][1 << MAXN];
const long long LLINF = 1LL * 1000000000 * 1000000000;
int n, m;
int mask(int x) { return 1 << x; }
bool contains(int s, int x) { return s & mask(x); }
long long rec(int i, int j) {
  if (dp[i][j] != -1) return dp[i][j];
  long long& res = dp[i][j];
  res = LLINF;
  for (int jj = j; jj > 0; jj = (jj - 1) & j) {
    if (contains(jj, i)) {
      int jprev = j - jj;
      if (contains(jprev, 0)) {
        for (int iprev = 0; iprev < (int)(n); iprev++) {
          if (contains(jprev, iprev) && cost[iprev][i] != -1) {
            long long curr = rec(iprev, jprev);
            for (int x = 0; x < (int)(n); x++) {
              for (int y = 0; y < (int)(n); y++) {
                if (contains(jprev, x) && contains(jj, y) && cost[x][y] != -1) {
                  if (x != iprev || y != i) {
                    curr += cost[x][y];
                  }
                }
              }
            }
            res = min(res, curr);
          }
        }
      }
    }
  }
  return res;
}
int main() {
  GI(n);
  GI(m);
  int a, b;
  long long c;
  memset(cost, -1, sizeof cost);
  for (int i = 0; i < (int)(m); i++) {
    GI(a);
    GI(b);
    GLL(c);
    a--;
    b--;
    cost[a][b] = c;
    cost[b][a] = c;
  }
  memset(dp, -1, sizeof dp);
  for (int j = 0; j < (int)(mask(n - 1)); j++) {
    dp[0][j] = 0;
  }
  cout << rec(n - 1, mask(n) - 1) << "\n";
  return 0;
}
