#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;

struct DisjointSet {
   DisjointSet(Int n)
      : ps(n, -1), ns(n, 1) {}
   std::vector<Int> ps, ns;
   Int find(Int x) {
      while( ps[x] != -1 ) x = ps[x];
      return x;
   }
   void unite(Int x, Int y) {
      x = find(x), y = find(y);
      if( x != y ) {
         if( not ( ns[x] <= ns[y] ) ) std::swap(x, y);
         ps[x] = y;
         ns[y] += ns[x];
      }
   }
};

int main() {
   Int v, e;
   std::cin >> v >> e;
   std::vector<Int> ss(e), ts(e), ws(e);
   rep(i, e) std::cin >> ss[i] >> ts[i] >> ws[i];
   std::vector<std::pair<Int, Int>> xs;
   rep(i, e) xs.emplace_back(ws[i], i);
   std::sort(xs.begin(), xs.end());
   DisjointSet z(v);
   Int res = 0;
   rep(i, e) {
      Int k = xs[i].second;
      Int s = ss[k], t = ts[k];
      guard( z.find(s) != z.find(t) );
      z.unite(s, t);
      res += ws[k];
   }
   printf("%ld\n", res);
}
#include "bits/stdc++.h"
  
using namespace std;

int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>>edge(N,vector<int>(N));
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;
    b--;
    edge[a][b]=c;
    edge[b][a]=c;
  }
  vector<int>box(1<<N);
  for(int i=0;i<1<<N;i++){
    for(int j=0;j<N;j++){
      if((i>>j)&1){
      	for(int k=j+1;k<N;k++){
          if((i>>k)&1)box[i]+=edge[j][k];
        }
      }
    }
  }
  vector<vector<int>>dp(1<<N,vector<int>(N,-1e9));
  for(int i=1;i<1<<N;i+=2)dp[i][0]=box[i];
  for(int i=1;i<1<<N;i+=2){
    for(int j=0;j<N;j++){
      if(!((i>>j)&1))continue;
      int bag=(1<<N)-1-i;
      int c=bag;
      while(c>0){
        for(int k=1;k<N;k++){
          if(!edge[j][k])continue;
          if((c>>k)&1) dp[i|c][k]=max(dp[i|c][k],dp[i][j]+edge[j][k]+box[c]);
        }
        c--;
        c&=bag;
      }
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++)ans+=edge[i][j];
  }
  cout<<ans-dp.back().back()<<endl;
}
