#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;
vl parent;
vl height;
void init(ll n) {
  parent.resize(n);
  iota(begin(parent), end(parent), 0);
  height.assign(n, 0);
}
ll Find(ll x) {
  if (x != parent[x]) parent[x] = Find(parent[x]);
  return parent[x];
}
bool Union(ll x, ll y) {
  x = Find(x), y = Find(y);
  if (x == y) return false;
  if (height[x] > height[y]) {
    parent[y] = x;
  } else {
    parent[x] = y;
    if (height[x] == height[y]) height[y]++;
  }
  return true;
}
vector<pair<ll, pll>> edges;
vb intree;
ll kruskal(ll n, ll k) {
  sort(begin(edges), end(edges));
  init(n);
  intree.assign(ll((edges).size()), false);
  ll res = 0;
  for (ll i = (0); i < (ll((edges).size())); i++) {
    intree[i] = Union(edges[i].second.first, edges[i].second.second);
    if (intree[i]) res += edges[i].first;
  }
  return count(begin(intree), end(intree), true) == k - 1 ? res : oo;
}
vvl adj;
vl comps;
void makeComps(ll cur, ll C, ll path) {
  if (comps[cur] != -1) return;
  if (path & (1 << cur)) return;
  comps[cur] = C;
  for (ll i = (0); i < (ll((adj).size())); i++) {
    if (adj[cur][i] != -1) {
      makeComps(i, C, path);
    }
  }
}
int main() {
  cin.sync_with_stdio(0);
  ll N, M;
  cin >> N >> M;
  adj.assign(N, vl(N, -1));
  for (ll i = (0); i < (M); i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    adj[a][b] = c;
    adj[b][a] = c;
  }
  ll ans = oo;
  for (ll path = 0; path < (1 << N); path++) {
    if (!(path & (1 << 0))) continue;
    if (!(path & (1 << (N - 1)))) continue;
    ({
      if (0) cerr << "TR: " << ("path") << " = " << (path) << endl;
    });
    edges.clear();
    ll su = 0;
    for (ll i = (0); i < (N); i++) {
      if (path & (1 << i)) {
        for (ll j = (i + 1); j < (N); j++) {
          if (path & (1 << j)) {
            if (adj[i][j] != -1) {
              ({
                if (0) cerr << "TR: " << ("i") << " = " << (i) << endl;
              });
              ({
                if (0) cerr << "TR: " << ("j") << " = " << (j) << endl;
              });
              ({
                if (0)
                  cerr << "TR: " << ("adj[i][j]") << " = " << (adj[i][j])
                       << endl;
              });
              edges.push_back({-adj[i][j], {i, j}});
              su += adj[i][j];
            }
          }
        }
      }
    }
    ll k = 0;
    for (ll i = (0); i < (N); i++)
      if (path & (1 << i)) k++;
    ll max_tree = kruskal(N, k);
    if (max_tree == -oo) continue;
    ({
      if (0) cerr << "TR: " << ("max_tree") << " = " << (max_tree) << endl;
    });
    max_tree += su;
    ({
      if (0) cerr << "TR: " << ("max_tree") << " = " << (max_tree) << endl;
    });
    comps.assign(N, -1);
    ll C = 0;
    for (ll i = (0); i < (N); i++) {
      if (path & (1 << i)) continue;
      if (comps[i] == -1) {
        makeComps(i, C++, path);
      }
    }
    vvl compEdges(C, vl(N, 0));
    for (ll i = (0); i < (N); i++) {
      if (comps[i] == -1) continue;
      for (ll j = (0); j < (N); j++) {
        if (comps[j] != -1) continue;
        if (adj[i][j] != -1) {
          compEdges[comps[i]][j] += adj[i][j];
        }
      }
    }
    ll res = max_tree;
    for (ll i = (0); i < (C); i++) {
      sort(begin(compEdges[i]), end(compEdges[i]));
      for (ll j = (0); j < (ll((compEdges[i]).size()) - 1); j++) {
        res += compEdges[i][j];
      }
    }
    ({
      if (0) cerr << "TR: " << ("res") << " = " << (res) << endl;
    });
    ans = min(res, ans);
  }
  cout << ans << endl;
}
