#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
using namespace std;
int er[20],p[20][20],sum[40000],dp[20][40000],n; 
V<int> v[40000];
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	int x,y,z,m;
	cin>>n>>m;
	FOR(i,1,m){
		cin>>x>>y>>z;p[x][y]=p[y][x]=z;
	}
	er[0]=1;
	FOR(i,1,n)er[i]=er[i-1]*2;
	FOR(i,1,er[n]-1){
		FOR(j,1,n)if(i&er[j-1])v[i].PB(j);
		sum[i]=sum[i^er[v[i][0]-1]];
		for(int j=1;j<v[i].size();j++){
			sum[i]+=p[v[i][0]][v[i][j]];
		}
	}
	FOR(i,0,er[n]-1)FOR(j,1,n)dp[j][i]=1000000000;
	dp[1][1]=0;
	FOR(mask,1,er[n]-1){
		FOR(i,1,n){
			if(!(mask&er[i-1])||dp[i][mask]>=1000000000)continue;
			FOR(j,1,n){
				if(mask&er[j-1]||!p[i][j])continue;
				dp[j][mask^er[j-1]]=min(dp[j][mask^er[j-1]],dp[i][mask]+sum[mask^er[i-1]^er[j-1]]-sum[mask^er[i-1]]);
			}
			int s=(er[n]-1)^mask,t=s;
			while(t){
				dp[i][mask^t]=min(dp[i][mask^t],dp[i][mask]+sum[mask^er[i-1]^t]-sum[mask^er[i-1]]-sum[t]);
				t=(t-1)&s;
			}
		}
	}
	cout<<dp[n][er[n]-1]<<'\n';
	RE 0;
}


