#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<pair<int, pair<int, int> > > edges;
vector<int> g[16];
bool vis[16];
int G[16][16];
int dp[1 << 13][15];
bool in(int x, int mask) {
  if (x == 1 || x == n) return true;
  return ((mask >> (x - 2)) & 1) != 0;
}
bool dfs(int c, int s, int mask) {
  if (c != s && in(c, mask)) {
    return false;
  }
  if (vis[c]) return true;
  vis[c] = true;
  bool res = true;
  for (int i = 0; i < g[c].size(); i++) {
    res &= dfs(g[c][i], s, mask);
    if (!res) break;
  }
  return res;
}
bool setB(int x, int mask) { return ((mask >> x) & 1) != 0; }
int f1(int mask) {
  int res = 0;
  for (int i = 1; i < n + 1; i++) g[i].clear();
  for (int i = 0; i < edges.size(); i++) {
    int u = edges[i].second.first;
    int v = edges[i].second.second;
    if (in(u, mask) && in(v, mask)) continue;
    g[u].push_back(v);
    g[v].push_back(u);
    bool ok = true;
    memset(vis, 0, sizeof(vis));
    for (int j = 1; j < n + 1; j++)
      if (in(j, mask)) {
        ok &= dfs(j, j, mask);
        if (!ok) break;
      }
    if (!ok) {
      g[u].pop_back();
      g[v].pop_back();
    } else {
      res += edges[i].first;
    }
  }
  return res;
}
int solve(int m, int p, int mask) {
  if (m == mask) {
    return G[p][n];
  }
  int &res = dp[m][p - 1];
  if (res != -1) {
    return res;
  }
  res = -INF;
  for (int i = 0; i < n - 2; i++)
    if (setB(i, mask) && !setB(i, m)) {
      res = max(res, solve(m | (1 << i), i + 2, mask) + G[p][i + 2]);
    }
  return res;
}
int f2(int mask) {
  for (int i = 1; i < n + 1; i++) {
    dp[0][i - 1] = -1;
    for (int m = mask; m; m = (m - 1) & mask) {
      dp[m][i - 1] = -1;
    }
  }
  return solve(0, 1, mask);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  int tot = 0;
  for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < n + 1; j++) {
      G[i][j] = -INF;
    }
  for (int i = 0; i < m; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    edges.push_back(make_pair(c, make_pair(u, v)));
    tot += c;
    G[u][v] = G[v][u] = c;
  }
  sort(edges.begin(), edges.end());
  reverse(edges.begin(), edges.end());
  if (n == 2) {
    printf("%d\n", 0);
    return 0;
  }
  int mx = 0;
  for (int i = 0; i < 1 << (n - 2); i++) {
    mx = max(mx, f1(i) + f2(i));
  }
  printf("%d\n", tot - mx);
  return 0;
}
