#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
const long long INF = 1ll << 50;
const double pi = acos(-1);
const double eps = 1e-8;
const long long mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
vector<vector<int> > g;
int main() {
  cin >> n >> m;
  g = vector<vector<int> >(n, vector<int>(n));
  int sum = 0, S = 1 << n;
  vector<int> dp(S);
  vector<vector<int> > DP(S, vector<int>(n));
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    sum += c;
    u--;
    v--;
    g[u][v] = c;
    g[v][u] = c;
  }
  for (int i = 1; i < S; i++)
    for (int j = 0; j < n; j++)
      for (int k = j + 1; k < n; k++)
        if (i & 1 << j && i & 1 << k) dp[i] += g[j][k];
  for (int i = 1; i < S; i++)
    for (int j = 0; j < n; j++)
      if (i & 1 << j && i % 2 == 1) {
        for (int k = 0; k < n; k++)
          if (!(i & 1 << k) && g[j][k])
            DP[i + (1 << k)][k] = max(DP[i + (1 << k)][k], DP[i][j] + g[j][k]);
        int T = S - i - 1, T_ = T;
        while (T) {
          DP[i + T][j] = max(DP[i + T][j], DP[i][j] + dp[T + (1 << j)]);
          T = (T - 1) & T_;
        }
      }
  cout << sum - DP[S - 1][n - 1] << endl;
}
