#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class union_find {
 private:
  std::vector<int> parent;
  std::vector<int> rank;
  std::vector<int> clump;

 public:
  union_find(int siz) {
    parent.resize(siz);
    rank.resize(siz);
    clump.resize(siz);
    for (int i = 0; i < siz; ++i) {
      parent[i] = i;
      rank[i] = 0;
      clump[i] = 1;
    }
  }
  void unite(int x, int y) {
    int xr = find(x);
    int yr = find(y);
    if (xr == yr) return;
    if (rank[xr] > rank[yr]) {
      parent[yr] = xr;
      clump[xr] += clump[yr];
    } else if (rank[yr] > rank[xr]) {
      parent[xr] = yr;
      clump[yr] += clump[xr];
    } else if (xr != yr) {
      parent[yr] = xr;
      clump[xr] += clump[yr];
      ++rank[xr];
    }
  }
  int find(int x) {
    if (parent[x] == x) {
      return x;
    } else {
      return parent[x] = find(parent[x]);
    }
  }
  bool check(int x, int y) { return find(x) == find(y); }
  int size(int x) { return clump[find(x)]; }
};
LL N, M;
LL cost[15][15] = {};
int main(void) {
  cin >> N >> M;
  LL total = 0;
  for (int i = 0; i < M; ++i) {
    LL a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    cost[a][b] = c;
    cost[b][a] = c;
    total += c;
  }
  LL maxtree = 0;
  LL three = 1;
  for (LL i = 0; i < N - 2; ++i) three *= 3;
  for (LL S = 0; S < three; ++S) {
    vector<int> X(1, 0), Y, Z(1, N - 1);
    Y.push_back(0);
    Y.push_back(N - 1);
    LL SS = S;
    for (int bit = 0; bit < N - 2; ++bit) {
      switch (SS % 3) {
        case 0:
          X.push_back(bit + 1);
          break;
        case 1:
          Y.push_back(bit + 1);
          break;
        case 2:
          Z.push_back(bit + 1);
          break;
      }
      SS /= 3;
    }
    LL tree = 0;
    for (int p : X)
      for (int q : X) {
        tree += cost[p][q];
      }
    for (int p : Z)
      for (int q : Z) {
        tree += cost[p][q];
      }
    tree /= 2;
    union_find uf(N);
    vector<pair<LL, pair<int, int>>> srt;
    for (int p : Y)
      for (int q : Y) {
        if (p >= q) continue;
        if (cost[p][q] == 0) continue;
        srt.push_back({cost[p][q], {p, q}});
      }
    sort(srt.begin(), srt.end());
    for (int j = srt.size() - 1; j >= 0; --j) {
      auto& p = srt[j];
      if (uf.check(p.second.first, p.second.second)) {
        continue;
      }
      tree += p.first;
      uf.unite(p.second.first, p.second.second);
    }
    maxtree = max(maxtree, tree);
  }
  cout << total - maxtree << endl;
  return 0;
}
