#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& a) {
  return os << "(" << a.first << "," << a.second << ")";
}
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << (*i) << " ";
  cout << endl;
}
template <class T>
bool chmin(T& a, const T& b) {
  return a > b ? (a = b, 1) : 0;
}
template <class T>
bool chmax(T& a, const T& b) {
  return a < b ? (a = b, 1) : 0;
}
int nextInt() {
  int x;
  scanf("%d", &x);
  return x;
}
int N;
int e[15][15];
long long memo[14400000];
long long dp[1 << 15][15];
int encode(int bs1, int bs2) {
  int res = 0;
  for (int i = 0, _n = (int)(N); i < _n; ++i) {
    res *= 3;
    if (bs1 >> i & 1)
      res += 1;
    else if (bs2 >> i & 1)
      res += 2;
  }
  return res;
}
long long cost(int bs1, int bs2) {
  int code = encode(bs1, bs2);
  if (memo[code] != -1) return memo[code];
  long long res = 0;
  if (bs1 == 0 || bs2 == 0) {
    res = 0;
  } else {
    int p1 = __builtin_ffs(bs1) - 1;
    res = cost(bs1 ^ (1 << p1), bs2);
    for (int p2 = 0, _n = (int)(N); p2 < _n; ++p2)
      if (bs2 >> p2 & 1) {
        res += e[p1][p2];
      }
  }
  return memo[code] = res;
}
int main2() {
  N = nextInt();
  int M = nextInt();
  memset(e, 0, sizeof(e));
  memset(memo, -1, sizeof(memo));
  for (int i = 0, _n = (int)(M); i < _n; ++i) {
    int a = nextInt() - 1;
    int b = nextInt() - 1;
    int c = nextInt();
    e[a][b] = e[b][a] = c;
  }
  for (int S = 0, _n = (int)(1 << N); S < _n; ++S)
    for (int t = 0, _n = (int)(N); t < _n; ++t) dp[S][t] = (1LL << 58);
  const int MASK = (1 << N) - 1;
  dp[1][0] = 0;
  for (int S = 1; S < (1 << N); S++) {
    for (int t = 0; t < N; t++)
      if (S >> t & 1) {
        for (int u = 0; u < N; u++)
          if (e[t][u] > 0) {
            if (S >> u & 1) {
            } else {
              chmin(dp[S | (1 << u)][u], dp[S][t] + cost(S ^ (1 << t), 1 << u));
            }
          }
        int co = (~S) & MASK;
        for (int T = co; T != 0; T = (T - 1) & co) {
          chmin(dp[S | T][t], dp[S][t] + cost(S ^ (1 << t), T));
        }
      }
  }
  long long ans = dp[(1 << N) - 1][N - 1];
  cout << ans << endl;
  return 0;
}
int main() {
  for (; !cin.eof(); cin >> ws) main2();
  return 0;
}
