#include <bits/stdc++.h>
using namespace std;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
template <typename T, typename U>
inline void mnze(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void mxze(T &x, U y) {
  if (x < y) x = y;
}
void _scan(int &x) { scanf("%d", &x); }
void _scan(long long &x) { scanf("%lld", &x); }
void _scan(double &x) { scanf("%lf", &x); }
void _scan(char &x) { scanf(" %c", &x); }
void _scan(char *x) { scanf("%s", x); }
void scan() {}
template <typename T, typename... U>
void scan(T &head, U &...tail) {
  _scan(head);
  scan(tail...);
}
template <typename T>
void _dbg(const char *sdbg, T h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename T, typename... U>
void _dbg(const char *sdbg, T h, U... t) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
const int MAXN = 15;
int n, m, c[MAXN][MAXN], con[MAXN][1 << MAXN], cli[1 << MAXN];
int dp[MAXN][1 << MAXN];
int f(int v, int msk) {
  if (v == n - 1) return con[n - 1][msk] + cli[msk];
  int &ret = dp[v][msk];
  if (ret != -1) return ret;
  ret = 0;
  if (c[v][n - 1]) mxze(ret, f(n - 1, msk) + c[v][n - 1]);
  for (int u = 0; u < (int)n; u++)
    if ((msk & (1 << u)) && c[v][u]) mxze(ret, f(u, msk ^ (1 << u)) + c[v][u]);
  for (int sub = msk; sub; sub = (sub - 1) & msk) {
    mxze(ret, f(v, msk ^ sub) + con[v][sub] + cli[sub]);
  }
  return ret;
}
int main() {
  scan(n, m);
  int CC = 0;
  for (int i = 0; i < (int)m; i++) {
    int a, b, cc;
    scan(a, b, cc);
    a--;
    b--;
    c[a][b] = c[b][a] = cc;
    CC += cc;
  }
  memset(dp, -1, sizeof(dp));
  for (int msk = 0; msk < (int)1 << n; msk++) {
    for (int i = 0; i < (int)n; i++)
      if (msk & (1 << i)) {
        for (int j = i + 1; j < (int)n; j++)
          if (msk & (1 << j)) {
            cli[msk] += c[i][j];
          }
      }
    for (int i = 0; i < (int)n; i++) {
      for (int j = 0; j < (int)n; j++)
        if (msk & (1 << j)) {
          con[i][msk] += c[i][j];
        }
    }
  }
  memset(dp, -1, sizeof(dp));
  (CC, f(0, (1 << (n - 1)) - 2));
  printf("%d\n", CC - f(0, (1 << (n - 1)) - 2));
}
