#include <bits/stdc++.h>
using namespace std;
const int maxn = 15 * 15;
int head[maxn], tot, n, cnt, m, vis[maxn], Sum, root[maxn];
struct Edge {
  int from, to, next, w;
} edge[maxn * 4], e[maxn];
void add(int x, int y, int w) {
  edge[++tot].to = y;
  edge[tot].next = head[x];
  edge[tot].w = w;
  head[x] = tot;
}
bool dfs(int x, int fa, int S) {
  if (x == n) {
    vis[x] = 1;
    return 1;
  }
  bool flag = 0;
  for (int i = head[x]; i; i = edge[i].next) {
    if (edge[i].to == fa || (S & (1 << (edge[i].to - 1)))) continue;
    if (dfs(edge[i].to, x, S | (1 << (edge[i].to - 1)))) {
      e[++cnt].from = x;
      e[cnt].to = edge[i].to;
      e[cnt].w = edge[i].w;
      vis[x] = 1;
      Sum += edge[i].w;
      flag = 1;
    }
  }
  return flag;
}
bool cmp(const Edge &a, const Edge &b) { return a.w > b.w; }
int findroot(int x) {
  if (x != root[x]) {
    root[x] = findroot(root[x]);
  }
  return root[x];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    add(x, y, w);
    add(y, x, w);
  }
  dfs(1, 0, 1);
  for (int i = 1; i <= n; i++) root[i] = i;
  sort(e + 1, e + cnt + 1, cmp);
  for (int i = 1; i <= cnt; i++) {
    int x = e[i].from, y = e[i].to;
    int ra = findroot(x), rb = findroot(y);
    if (ra == rb) continue;
    Sum -= e[i].w;
    root[ra] = rb;
  }
  printf("%d\n", Sum);
  return 0;
}
