#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[15];
int n, m, ans, b[65536], dp[15][65536];
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, len;
    cin >> x >> y >> len;
    x--;
    y--;
    v[x].push_back(make_pair(y, len));
    v[y].push_back(make_pair(x, len));
    ans += len;
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++)
      if (!(i & (1 << j)) && !b[i + (1 << j)]) {
        b[i + (1 << j)] = b[i];
        for (int k = 0; k < v[j].size(); k++)
          if (i & (1 << v[j][k].first)) b[i + (1 << j)] += v[j][k].second;
      }
  }
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
      if (dp[i][j] != -1 && (i & 1 << j)) {
        for (int k = 0; k < v[j].size(); k++)
          if (!(i & (1 << v[j][k].first)))
            dp[i | (1 << v[j][k].first)][v[j][k].first] =
                max(dp[i | (1 << v[j][k].first)][v[j][k].first],
                    dp[i][j] + v[j][k].second);
        for (int k = ((1 << n) - 1 - i) | (1 << j); k;
             k = (k - 1) & (((1 << n) - 1 - i) | (1 << j)))
          if (k & (1 << j)) dp[i | k][j] = max(dp[i | k][j], dp[i][j] + b[k]);
      }
  cout << ans - dp[(1 << n) - 1][n - 1];
}
