#include <bits/stdc++.h>
using namespace std;
const int N = 16, M = 140;
int n, m, cnt, fa[N], f[N], head[N], to[N << 1], nxt[N << 1], dfn[N], out[N],
    tim, sum, ans, res;
inline void add(int a, int b) {
  to[++cnt] = b;
  nxt[cnt] = head[a];
  head[a] = cnt;
}
struct Edge {
  int a, b, c;
  inline bool operator<(const Edge &o) const { return c > o.c; }
} e[M];
inline int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
bool in[N], vis[N], flag;
inline void dfs(int x) {
  if (!flag) vis[x] = true;
  if (x == n) flag = true;
  dfn[x] = ++tim;
  for (register int i = head[x]; i; i = nxt[i])
    if (to[i] != f[x]) {
      f[to[i]] = x;
      dfs(to[i]);
    }
  out[x] = tim;
  if (!flag) vis[x] = false;
}
clock_t st = clock();
int main() {
  srand(20050915);
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= m; i++)
    scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c), sum += e[i].c;
  sort(e + 1, e + m + 1);
  while (true) {
    res = tim = flag = cnt = 0;
    memset(head, 0, sizeof head);
    memset(vis, 0, sizeof vis);
    memset(in, 0, sizeof in);
    memset(f, 0, sizeof f);
    for (register int i = 1; i <= n; i++) fa[i] = i;
    for (register int i = 1, j = 1; i <= m && j < n; i++) {
      int fa1 = getfa(e[i].a), fa2 = getfa(e[i].b);
      in[i] = false;
      if (fa1 != fa2) {
        in[i] = true;
        fa[fa1] = fa2;
        add(e[i].a, e[i].b);
        add(e[i].b, e[i].a);
        res += e[i].c;
        ++j;
      }
    }
    dfs(1);
    for (register int i = 1; i <= m; i++)
      if (!in[i] && !vis[e[i].a] && !vis[e[i].b]) res += e[i].c;
    ans = max(ans, res);
    random_shuffle(e + 1, e + m + 1);
    if (clock() - st >= CLOCKS_PER_SEC * 3.9) break;
  }
  printf("%d", sum - ans);
}
