#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int> > ls(n);
  vector<int> as(m), bs(m), cs(m);
  for (int i = 0; i < (m); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    as[i] = a;
    bs[i] = b;
    cs[i] = c;
    ls[a].push_back(i);
    ls[b].push_back(i);
  }
  map<int, long long> mem;
  function<long long(int, int, int)> f = [&](int s, int t, int msk) {
    if (s == t) return 0LL;
    if (s > t) swap(s, t);
    int hsh = msk * n * n + n * s + t;
    if (!mem.count(hsh)) {
      long long ans = inf;
      for (auto &ix : ls[s]) {
        int u = as[ix] + bs[ix] - s;
        if (!(msk & (1 << u))) continue;
        int rem = msk - (1 << s) - (1 << t);
        if (u != t) rem -= 1 << u;
        for (int sub = rem;;) {
          int B = sub + (1 << t);
          if (t != u) B += 1 << u;
          int A = msk - B;
          long long cur = -cs[ix];
          for (int i = 0; i < (m); ++i)
            if (((A & (1 << as[i])) && (B & (1 << bs[i]))) ||
                ((A & (1 << bs[i])) && (B & (1 << as[i]))))
              cur += cs[i];
          cur += f(u, t, B);
          ans = min(ans, cur);
          if (sub == 0) break;
          sub = (sub - 1) & rem;
        }
      }
      return mem[hsh] = ans;
    }
    return mem[hsh];
  };
  cout << f(0, n - 1, (1 << n) - 1) << endl;
}
