#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g;
class union_find {
 public:
  union_find(int n) {
    for (int i = 0; i < n; i++) {
      v.push_back(i);
    }
  }
  int find(int i) {
    if (v[i] == i) return i;
    return v[i] = find(v[i]);
  }
  void unite(int i, int j) { v[find(i)] = find(j); }
  vector<int> v;
};
int main() {
  cin.tie(0);
  cin >> n >> m;
  g = vector<vector<int>>(n, vector<int>(n, -1));
  vector<pair<int, pair<int, int>>> es(m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    g[a][b] = c;
    g[b][a] = c;
    es.emplace_back(c, make_pair(a, b));
  }
  sort(es.rbegin(), es.rend());
  int64_t ans = 0x7ffffffffffffffL;
  for (int b = 0; b < (1 << n); b++) {
    {
      union_find uf(n);
      for (int i = 0; i < n; i++) {
        if (!(b & (1 << i))) continue;
        for (int j = i + 1; j < n; j++) {
          if (!(b & (1 << j))) continue;
          if (g[i][j] < 0) continue;
          uf.unite(i, j);
        }
      }
      if (uf.find(0) != uf.find(n - 1)) {
        continue;
      }
    }
    int64_t cur = 0;
    {
      union_find uf(n);
      for (int i = 0; i < m; i++) {
        int c = es[i].first;
        int f = es[i].second.first;
        int t = es[i].second.second;
        if (!((b & (1 << f)) && (b & (1 << t)))) continue;
        if (uf.find(f) == uf.find(t)) {
          cur += c;
          continue;
        }
        uf.unite(f, t);
      }
    }
    union_find uf(n);
    for (int i = 0; i < m; i++) {
      int c = es[i].first;
      int f = es[i].second.first;
      int t = es[i].second.second;
      if (((b & (1 << f)) && (b & (1 << t)))) continue;
      int ra = uf.find(f);
      int rb = uf.find(t);
      int ia = -1, ib = -1;
      for (int i = 0; i < n; i++) {
        if (!(b & (1 << i))) continue;
        int r = uf.find(i);
        if (r == ra) {
          ia = i;
        }
        if (r == rb) {
          ib = i;
        }
      }
      if (ia >= 0 && ib >= 0 && ia != ib) {
        cur += c;
        continue;
      }
      uf.unite(f, t);
    }
    ans = min(ans, cur);
  }
  cout << ans << endl;
  return 0;
}
