#include <bits/stdc++.h>
using namespace std;
const int Maxn = 16;
int n, m;
vector<pair<int, pair<int, int> > > E;
int par[Maxn], siz[Maxn];
int col[Maxn];
int sum;
int getPar(int x) { return x == par[x] ? x : par[x] = getPar(par[x]); }
bool unionSet(int a, int b) {
  a = getPar(a);
  b = getPar(b);
  if (a == b) return false;
  if (siz[a] >= siz[b]) {
    siz[a] += siz[b];
    par[b] = a;
  } else {
    siz[b] += siz[a];
    par[a] = b;
  }
  return true;
}
int Solve(int cols) {
  if (col[1] == col[n]) return 0;
  int res = 0;
  for (int i = 1; i <= cols; i++) {
    par[i] = i;
    siz[i] = 1;
  }
  for (int i = 0; i < E.size(); i++)
    if (col[E[i].second.first] == col[E[i].second.second])
      res += E[i].first;
    else if (unionSet(col[E[i].second.first], col[E[i].second.second]))
      res += E[i].first;
  return res;
}
int Gen(int v, int cols) {
  if (v > n) return Solve(cols);
  int res = 0;
  for (int i = 1; i <= cols; i++) {
    col[v] = i;
    res = max(res, Gen(v + 1, cols));
  }
  col[v] = cols + 1;
  res = max(res, Gen(v + 1, cols + 1));
  return res;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    E.push_back(pair<int, pair<int, int> >(c, pair<int, int>(a, b)));
    sum += c;
  }
  sort(E.rbegin(), E.rend());
  printf("%d\n", sum - Gen(1, 0));
  return 0;
}
