#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[150], b[150], c[150];
tuple<int, int, int> edge[150];
vector<int> et[15];
vector<int> ec[15];
int gid[15];
void input() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    et[a[i]].push_back(b[i]);
    et[b[i]].push_back(a[i]);
    ec[a[i]].push_back(c[i]);
    ec[b[i]].push_back(c[i]);
    edge[i] = tuple<int, int, int>(c[i], a[i], b[i]);
  }
  sort(edge, edge + m, greater<tuple<int, int, int> >());
}
bool regal(int g) {
  queue<int> que;
  bool used[15] = {false};
  bool cango[15] = {false};
  for (int i = 1; i < n - 1; i++) {
    cango[i] = (gid[i] == g);
  }
  if (g == 0) {
    cango[0] = true;
  }
  if (g == 1) {
    cango[0] = true;
    cango[n - 1] = true;
  }
  if (g == 2) {
    cango[n - 1] = true;
  }
  if (g <= 1) {
    que.push(0);
    used[0] = true;
  } else {
    que.push(n - 1);
    used[n - 1] = true;
  }
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (int i = 0; i < et[v].size(); i++) {
      int nv = et[v][i];
      if (used[nv] || !cango[nv]) continue;
      que.push(nv);
      used[nv] = true;
    }
  }
  for (int i = 0; i < n; i++) {
    if (cango[i] && !used[i]) return false;
  }
  return true;
}
class UF {
  int par[15];
  int sz[15];

 public:
  void init(int n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      sz[i] = 1;
    }
  }
  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  bool same(int x, int y) { return par[root(x)] == par[root(y)]; }
  void marge(int x, int y) {
    x = root(x);
    y = root(y);
    if (sz[x] < sz[y]) {
      par[x] = y;
      sz[y] += sz[x];
    } else {
      par[y] = x;
      sz[x] += sz[y];
    }
  }
} uf;
int mst() {
  int ret = 0;
  bool cango[15] = {false};
  for (int i = 1; i < n - 1; i++) {
    cango[i] = (gid[i] == 1);
  }
  cango[0] = true;
  cango[n - 1] = true;
  uf.init(n);
  for (int i = 0; i < m; i++) {
    if (!cango[get<1>(edge[i])] || !cango[get<2>(edge[i])]) {
      continue;
    }
    if (!uf.same(get<1>(edge[i]), get<2>(edge[i]))) {
      uf.marge(get<1>(edge[i]), get<2>(edge[i]));
      ret += get<0>(edge[i]);
    }
  }
  return ret;
}
int getCost(int debug = 0) {
  int i;
  int cst = 0;
  for (i = 0; i < m; i++) {
    if (gid[a[i]] != gid[b[i]]) {
      cst += c[i];
    }
    if (gid[a[i]] == gid[b[i]] && gid[a[i]] == 1) {
      cst += c[i];
    }
  }
  cst -= mst();
  return cst;
}
int main() {
  int pow3[20];
  int i, j;
  pow3[0] = 1;
  for (i = 1; i < 20; i++) pow3[i] = pow3[i - 1] * 3;
  input();
  int ans = 1e+9;
  for (i = 0; i < pow3[n - 2]; i++) {
    gid[0] = 0;
    for (j = 0; j < n - 2; j++) {
      gid[j + 1] = (i / pow3[j]) % 3;
    }
    gid[n - 1] = 2;
    if (!regal(0)) continue;
    if (!regal(1)) continue;
    if (!regal(2)) continue;
    int cst = getCost(i);
    ans = min(ans, cst);
  }
  cout << ans << endl;
  return 0;
}
