#include <bits/stdc++.h>
int checked[40000][16];
long long dp[40000][16];
long long esum[40000];
using namespace std;
int eds[16][16];
int n, m;
long long calc(int state, int now);
long long calc_sub(int state_base, int state, int dep, int now, int prev) {
  if (dep == n)
    return esum[state_base - state] + eds[now][prev] + calc(state, prev);
  long long ret = 0;
  if (dep == prev) {
    ret = calc_sub(state_base, state + (1 << dep), dep + 1, now, prev);
  } else if (dep == now) {
    ret = calc_sub(state_base, state, dep + 1, now, prev);
  } else {
    ret = calc_sub(state_base, state, dep + 1, now, prev);
    if (state_base & (1 << dep)) {
      long long temp =
          calc_sub(state_base, state + (1 << dep), dep + 1, now, prev);
      if (ret < temp) ret = temp;
    }
  }
  return ret;
}
long long calc(int state, int now) {
  if (checked[state][now]) return dp[state][now];
  checked[state][now] = 1;
  if (now == 0) {
    dp[state][now] = esum[state];
  } else {
    dp[state][now] = 0;
    for (int i = 0; i < n; i++) {
      if ((state & (1 << i)) > 0 && i != now && eds[i][now] > 0) {
        long long temp = calc_sub(state, 1, 1, now, i);
        if (dp[state][now] < temp) dp[state][now] = temp;
      }
    }
  }
  return dp[state][now];
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int va, vb, vc;
    cin >> va >> vb >> vc;
    va--;
    vb--;
    eds[va][vb] = vc;
    eds[vb][va] = vc;
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++)
      for (int k = j + 1; k < n; k++) {
        if ((i & (1 << j)) > 0 && (i & (1 << k)) > 0) esum[i] += eds[j][k];
      }
  }
  cout << esum[(1 << n) - 1] - calc((1 << n) - 1, n - 1) << endl;
  return 0;
}
