#include <bits/stdc++.h>
using namespace std;
int ans = 1e9, t, n, m, fa[20], a[20][20], _;
const double delta = 0.993;
vector<int> g[20];
bool vis[20], use[20], p[20][20];
struct ed {
  int u, v, w;
} e[20 * 20], tmp[20 * 20];
void dfs(int x, int f) {
  fa[x] = f;
  for (auto to : g[x])
    if (to != f) dfs(to, x);
}
bool cmp(const ed &x, const ed &y) { return x.w > y.w; }
void dfs2(int rt, int x, int f, int cnt) {
  if (cnt == 1 && ~a[x][rt] && !p[x][rt] && !(vis[x] && vis[rt])) _ += a[x][rt];
  for (auto to : g[x])
    if (to != f) dfs2(rt, to, x, cnt + vis[to]);
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int solve() {
  int tot = 0;
  _ = 0;
  for (int i = (1); i <= (n); ++i) fa[i] = i, vis[i] = 0;
  for (int i = (1); i <= (n); ++i)
    for (int j = (1); j <= (n); ++j) p[i][j] = 0;
  for (int i = (1); i <= (m); ++i) use[i] = 0;
  for (int i = (1); i <= (m); ++i) {
    int u = find(tmp[i].u), v = find(tmp[i].v);
    if (u == v) continue;
    if (u > v) swap(u, v);
    fa[v] = u;
    tot += tmp[i].w, use[i] = 1,
                     p[tmp[i].u][tmp[i].v] = p[tmp[i].v][tmp[i].u] = 1;
  }
  for (int i = (1); i <= (n); ++i) g[i].clear();
  for (int i = (1); i <= (m); ++i)
    if (use[i])
      g[tmp[i].u].push_back(tmp[i].v), g[tmp[i].v].push_back(tmp[i].u);
  for (int i = (1); i <= (n); ++i) fa[i] = 0;
  dfs(1, 0);
  for (int i = n; i; i = fa[i]) vis[i] = 1;
  for (int i = (1); i <= (n); ++i) dfs2(i, i, 0, vis[i]);
  tot += _ / 2;
  return tot;
}
void Rand() {
  random_shuffle(tmp + 1, tmp + m + 1);
  ans = max(ans, solve());
}
int main() {
  int qwq = 0, u, v, w;
  srand(23336666);
  srand(rand());
  srand(rand());
  scanf("%d%d", &n, &m);
  memset(a, -1, sizeof(a));
  for (int i = (1); i <= (m); ++i) {
    scanf("%d%d%d", &u, &v, &w);
    e[i] = (ed){u, v, w}, qwq += w, a[u][v] = a[v][u] = w;
    tmp[i] = e[i], g[u].push_back(v), g[v].push_back(u);
  }
  sort(e + 1, e + m + 1, cmp);
  for (int i = (1); i <= (m); ++i) tmp[i] = e[i];
  ans = solve();
  for (int i = (1); i <= (600500); ++i) Rand();
  printf("%d\n", qwq - ans);
}
