#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long mx = INT_MAX;
const long double pi = 4 * atan((long double)1);
const long long mxN = 16;
long long n, m;
long long masksum[1 << mxN], edge[mxN][mxN], dp[mxN][1 << mxN], summ;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  memset(dp, -1, sizeof(dp));
  for (long long i = 1; i <= m; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edge[u][v] = edge[v][u] = w;
    summ += w;
    for (long long j = 0; j < (1 << n); j++)
      if ((j >> u & 1) and (j >> v & 1)) masksum[j] += w;
  }
  dp[1][0] = 0;
  for (long long i = 1; i < (1 << n); i++) {
    for (long long j = 0; j < n; j++) {
      if (~dp[i][j]) {
        for (long long k = 0; k < n; k++)
          if (!(i >> k & 1) and edge[j][k])
            dp[i | (1 << k)][k] =
                max(dp[i | (1 << k)][k], dp[i][j] + edge[j][k]);
        for (long long all = ((1 << n) - 1) ^ i, k = all; k; k = (k - 1) & all)
          dp[i | k][j] = max(dp[i | k][j], dp[i][j] + masksum[k | (1 << j)]);
      }
    }
  }
  cout << summ - dp[(1 << n) - 1][n - 1];
}
