#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e9;
struct Edge {
  int to;
  ll w;
};
using Graph = vector<vector<Edge>>;
int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n);
  ll sumall = 0;
  for (int i = 0; i < m; i++) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    sumall += c;
    a--, b--;
    g[a].push_back(Edge{b, c});
    g[b].push_back(Edge{a, c});
  }
  vector<ll> sc(1 << n, 0LL);
  for (int i = 0; i < (1 << n); i++) {
    ll sum = 0;
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        for (int k = 0; k < g[j].size(); k++) {
          if ((i >> g[j][k].to) & 1) sum += g[j][k].w;
        }
      }
    }
    sc[i] = sum / 2;
  }
  vector<vector<ll>> dp(1 << n, vector<ll>(n, -INF));
  dp[1][0] = 0;
  for (int bit = 1; bit < (1 << n); bit++) {
    int sup = ((1 << n) - 1) & (~bit);
    for (int j = 0; j < n; j++) {
      if (!((bit >> j) & 1)) continue;
      if (j == n - 1) {
        dp[(1 << n) - 1][n - 1] = max(
            dp[(1 << n) - 1][n - 1], dp[bit][n - 1] + sc[sup + (1 << (n - 1))]);
      } else {
        int sub = sup;
        do {
          for (int k = 0; k < g[j].size(); k++) {
            if ((sub >> g[j][k].to) & 1) {
              dp[sub | bit][g[j][k].to] =
                  max(dp[sub | bit][g[j][k].to],
                      dp[bit][j] + g[j][k].w +
                          sc[(1 << j) ^ sub ^ (1 << g[j][k].to)]);
            }
          }
          sub = (sub - 1) & sup;
        } while (sub != sup);
      }
    }
  }
  cout << sumall - dp[(1 << n) - 1][n - 1] << endl;
  return 0;
}
