#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int> > g[15];
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a].push_back(pair<int, int>(b, c));
    g[b].push_back(pair<int, int>(a, c));
  }
  int dp[14][14][1 << 14];
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1; j++) {
      if (i == j)
        fill(dp[i][j], dp[i][j] + (1 << n), 0);
      else
        fill(dp[i][j], dp[i][j] + (1 << n), INF);
    }
  }
  for (int i = 1; i < (1 << (n - 1)); i++) {
    for (int j = i; j > 0; j = (j - 1) & i) {
      int sum = 0;
      for (int x = 0; x < n - 1; x++) {
        if ((j & (1 << x)) == 0) continue;
        for (auto pr : g[x]) {
          int y = pr.first;
          if (((i - j) & (1 << y)) == 0) continue;
          sum += pr.second;
        }
      }
      for (int x = 0; x < n - 1; x++) {
        if ((j & (1 << x)) == 0) continue;
        for (auto pr : g[x]) {
          int y = pr.first;
          if (((i - j) & (1 << y)) == 0) continue;
          for (int z = 0; z < n - 1; z++) {
            if (((i - j) & (1 << z)) == 0) continue;
            dp[x][z][i] = min(dp[x][z][i], dp[y][z][i - j] + sum - pr.second);
          }
        }
      }
    }
  }
  int ans = INF;
  for (int i = 1; i < (1 << (n - 1)); i++) {
    int sum = 0;
    for (int x = 0; x < n - 1; x++) {
      if ((i & (1 << x)) == 0) continue;
      for (auto pr : g[x]) {
        int y = pr.first;
        if ((((1 << n) - 1 - i) & (1 << y)) == 0) continue;
        sum += pr.second;
      }
    }
    for (auto pr : g[n - 1]) {
      int y = pr.first;
      if ((i & (1 << y)) == 0) continue;
      ans = min(ans, dp[0][y][i] + sum - pr.second);
    }
  }
  cout << ans << endl;
  return 0;
}
