#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 29;
const long long INF = 1ll << 58;
const double pi = acos(-1);
const double eps = 1e-7;
const long long mod = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int n, m;
vector<vector<pair<int, int> > > g;
int main() {
  cin >> n >> m;
  g = vector<vector<pair<int, int> > >(n);
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    u--;
    v--;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  int U = 1 << n;
  vector<vector<int> > dp(U, vector<int>(n));
  vector<int> DP(U);
  for (int i = 0; i < U; i++)
    for (int j = 0; j < n; j++)
      if (i & 1 << j) {
        DP[i] = DP[i - (1 << j)];
        for (int k = 0; k < g[j].size(); k++) {
          pair<int, int> p = g[j][k];
          int v = p.first, c = p.second;
          if (i & 1 << v) DP[i] += c;
        }
      }
  for (int i = 0; i < U; i++)
    for (int j = 1; j < n; j++)
      if (i & 1 << j) {
        dp[i][j] = inf;
        if (i % 2 == 0) continue;
        int S = i - (1 << j), T = S;
        do {
          int sum = 0;
          for (int k = 0; k < g[j].size(); k++) {
            int v = g[j][k].first, c = g[j][k].second;
            if (T & 1 << v) sum += g[j][k].second;
          }
          for (int k = 0; k < g[j].size(); k++) {
            pair<int, int> p = g[j][k];
            int v = p.first, c = p.second;
            if (T & 1 << v) {
              dp[i][j] =
                  min(dp[i][j], dp[S - T + (1 << v)][v] + DP[S - (1 << v)] -
                                    DP[T - (1 << v)] - 2 * DP[S - T] +
                                    DP[S - T + (1 << j)] + sum - c);
            }
          }
          T = S & (T - 1);
        } while (T != S);
      }
  cout << dp[U - 1][n - 1] << endl;
}
