#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 20, MASK = (1 << 15) + 5;
int n, m, dp[N][MASK], cost[MASK];
vector<pair<int, int> > g[N];
struct Edge {
  int u, v, c;
  Edge(int u = -1, int v = -1, int c = -1) : u(u), v(v), c(c){};
};
vector<Edge> e;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    g[u].push_back(pair<int, int>(v, c)), g[v].push_back(pair<int, int>(u, c));
    e.push_back(Edge(u, v, c));
  }
  for (int mask = 0; mask < (1 << n); mask++) {
    cost[mask] = 0;
    for (auto j : e) {
      int u = j.u, v = j.v;
      if (((mask >> u) & 1) == ((mask >> v) & 1)) continue;
      cost[mask] += j.c;
    }
  }
  memset(dp, 63, sizeof dp);
  for (int layer = 0; layer < (1 << n); layer++)
    if (layer & 1) {
      dp[0][layer] = cost[layer];
    }
  for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++)
      if (dp[i][mask] != inf) {
        int otherMask = ((1 << n) - 1) ^ mask;
        for (auto j : g[i])
          if (!(mask & (1 << j.first))) {
            int v = j.first;
            for (int submask = otherMask; submask >= 0;
                 submask = ((submask - 1) & otherMask)) {
              if (submask == 0) break;
              if (!(submask & (1 << v))) continue;
              dp[v][mask | submask] =
                  min(dp[v][mask | submask],
                      dp[i][mask] + cost[submask] - 2 * j.second);
            }
          }
      }
  int finalAns = dp[n - 1][(1 << n) - 1];
  assert(finalAns % 2 == 0);
  cout << (finalAns >> 1);
  return 0;
}
