#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void input(T &x) {
  register char c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline long long bigmod(long long p, long long e, long long M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
const int N = 1001;
int n, u, v, w, m;
int dp[15][1 << 15][2];
bool vis[15][1 << 15];
int A[15][15];
void solve(int now, int mask) {
  if (now == n - 1) {
    dp[now][mask][0] = 1e9;
    dp[now][mask][1] = 0;
    return;
  }
  if (vis[now][mask]) return;
  vis[now][mask] = 1;
  dp[now][mask][0] = 0;
  dp[now][mask][1] = 1e9;
  vector<int> vec;
  for (int i = 0; i < n; i++) {
    if (A[now][i] && (mask & (1 << i)) == 0) {
      int nmask = mask | (1 << i);
      solve(i, mask | (1 << i));
      dp[now][mask][0] += min(dp[i][nmask][0], A[now][i]);
      vec.push_back(i);
    }
  }
  for (auto x : vec) {
    int nmask = mask | (1 << x);
    int q = dp[now][mask][0] - min(dp[x][nmask][0], A[now][x]);
    q += dp[x][nmask][1];
    dp[now][mask][1] = min(dp[now][mask][1], q);
  }
  return;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v >> w;
    u--, v--;
    A[u][v] = A[v][u] = w;
  }
  memset(dp, -1, sizeof(dp));
  solve(0, 1);
  cout << dp[0][1][1] << endl;
  return 0;
}
