#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using lli = long long;
int n, m;
vector<pii> adj[20];
inline bool isin(int s, int v) { return s >> v & 1; }
int pa[20];
inline int find(int cur) {
  return cur == pa[cur] ? cur : pa[cur] = find(pa[cur]);
}
void merge(int u, int v) {
  u = find(u);
  v = find(v);
  if (u != v) pa[v] = u;
}
int solve(int s) {
  int cs = 0;
  for (int i = 0; i < n; i++) pa[i] = i;
  for (int i = 0; i < n; i++)
    if (!isin(s, i)) {
      for (auto &it : adj[i])
        if (!isin(s, it.second)) {
          merge(i, it.second);
          cs += it.first;
        }
    }
  cs /= 2;
  for (int i = 0; i < n; i++)
    if (!isin(s, i) && find(i) == i) {
      int mx[15] = {
          0,
      };
      for (int j = 0; j < n; j++)
        if (find(i) == find(j)) {
          for (auto &it : adj[j])
            if (isin(s, it.second)) mx[it.second] += it.first;
        }
      int mm = 0;
      for (int i = 0; i < n; i++) mm = max(mm, mx[i]);
      cs += mm;
    }
  return cs;
}
int dist[1 << 15];
int arr[15][15];
int main() {
  int cs = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--;
    v--;
    adj[u].push_back(pii(w, v));
    adj[v].push_back(pii(w, u));
    arr[u][v] = arr[v][u] = w;
    cs += w;
  }
  const int INF = 1e9;
  for (int i = 0; i < 1 << n; i++) dist[i] = -INF;
  dist[1] = 0;
  int ans = 0;
  for (int s = 0; s < 1 << n; s++) {
    for (int j = 0; j < n; j++)
      if (s >> j & 1) {
        for (int k = 0; k < n; k++)
          if (k != j && isin(s, k) && arr[k][j] != 0) {
            dist[s] = max(dist[s], dist[s ^ (1 << j)] + arr[k][j]);
          }
      }
    if (dist[s] >= 0 && isin(s, n - 1)) {
      ans = max(ans, dist[s] + solve(s));
    }
  }
  printf("%d\n", cs - ans);
  return 0;
}
