#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
const int maxn = 16;
int dp[1 << maxn][maxn], dp2[1 << maxn], n, m, cost[maxn][maxn];
vector<int> g[1 << maxn];
vector<int> get_msk(int mask) {
  vector<int> v, v2;
  for (int i = 0; i < n; i++)
    if (!(mask & (1 << i))) v.push_back(i);
  for (int msk2 = 0; msk2 < (1 << (int)v.size()); msk2++) {
    int msk3 = 0;
    for (int i = 0; i < v.size(); i++)
      if (msk2 & (1 << i)) msk3 |= 1 << v[i];
    if (msk3 != 0) g[mask].push_back(msk3);
  }
  return v2;
}
int main() {
  for (int i = 0; i < maxn; i++)
    for (int j = 0; j < maxn; j++) cost[i][j] = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    u--;
    v--;
    cost[u][v] = c;
    cost[v][u] = c;
  }
  for (int mask = 0; mask < (1 << n); mask++) get_msk(mask);
  for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if ((mask & (1 << i)) && (mask & (1 << j)))
          dp2[mask] = dp2[mask] + cost[i][j];
  for (int mask = 0; mask < (1 << n); mask++) dp2[mask] = dp2[mask] / 2;
  for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++) dp[mask][i] = -inf;
  dp[1 << 0][0] = 0;
  for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++) {
      if ((dp[mask][i] == -inf) || !(mask & (1 << i))) continue;
      for (int k = 0; k < g[mask].size(); k++) {
        int mask2 = g[mask][k];
        for (int j = 0; j < n; j++) {
          if (mask2 & (1 << j) && cost[i][j] > 0) {
            dp[mask | mask2][j] =
                max(dp[mask | mask2][j], dp[mask][i] + cost[i][j] + dp2[mask2]);
          }
        }
      }
    }
  printf("%d\n", dp2[(1 << n) - 1] - dp[(1 << n) - 1][n - 1]);
  return 0;
}
