#include <bits/stdc++.h>
using namespace std;
int n, m, head[20], fa[20];
int ans = 0, sum = 0, son, o = 0, tmp = INT_MAX;
bool vis[20], used[210];
int find(int a) { return fa[a] == a ? a : fa[a] = find(fa[a]); }
struct edge_sum {
  int u, v, w;
  bool operator<(const edge_sum &b) const { return w > b.w; }
} e_s[210];
struct edge {
  int to, link;
} e[210];
void add_edge(int u, int v) {
  e[++o].link = head[u], head[u] = o, e[o].to = v;
  e[++o].link = head[v], head[v] = o, e[o].to = u;
}
bool dfs(int u, int pre) {
  if (u == n) return true;
  for (int i = head[u]; i; i = e[i].link) {
    if (e[i].to == pre) continue;
    if (dfs(e[i].to, u)) {
      if (u == 1) son = e[i].to;
      return true;
    }
  }
}
void work(int u, int pre) {
  vis[u] = true;
  for (int i = head[u]; i; i = e[i].link) {
    if (e[i].to == pre) continue;
    work(e[i].to, u);
  }
}
void clear() {
  for (int i = 1; i <= m; i++) used[i] = false;
  for (int i = 1; i <= n; i++) vis[i] = false, head[i] = 0, fa[i] = i;
  ans = 0;
  o = 0;
}
int main() {
  srand(20050818);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++)
    scanf("%d %d %d", &e_s[i].u, &e_s[i].v, &e_s[i].w), sum += e_s[i].w;
  for (int t = 1; t <= 100000; t++) {
    clear();
    random_shuffle(e_s + 1, e_s + m + 1);
    for (int i = 1; i <= m; i++) {
      int u_f = find(e_s[i].u), v_f = find(e_s[i].v);
      if (u_f == v_f) continue;
      fa[u_f] = v_f;
      add_edge(e_s[i].u, e_s[i].v);
      ans += e_s[i].w;
      used[i] = true;
    }
    dfs(1, 0);
    for (int i = head[1]; i; i = e[i].link) {
      if (e[i].to == son) {
        work(e[i].to, 1);
        break;
      }
    }
    for (int i = 1; i <= m; i++) {
      if (used[i] || vis[e_s[i].u] || vis[e_s[i].v]) continue;
      ans += e_s[i].w;
    }
    tmp = min(tmp, sum - ans);
  }
  printf("%d\n", tmp);
}
