#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >v[15];
int n,m,ans,b[65536],dp[65536][15];
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y,len;cin>>x>>y>>len;x--;y--;
		v[x].push_back(make_pair(y,len));v[y].push_back(make_pair(x,len));
		ans+=len; 
	}
	for(int i=0;i<(1<<n);i++)
	{
		for(int j=0;j<n;j++)
			if(!(i&(1<<j))&&!b[i+(1<<j)])
			{
				b[i+(1<<j)]=b[i];
				for(int k=0;k<v[j].size();k++)
					if(i&(1<<v[j][k].first))
						b[i+(1<<j)]+=v[j][k].second;
			}
	}
	memset(dp,-1,sizeof(dp));
	dp[1][0]=0;
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			if(dp[i][j]!=-1&&(i&1<<j)){
				for(int k=0;k<v[j].size();k++)
					if(!(i&(1<<v[j][k].first)))
						dp[i|(1<<v[j][k].first)][v[j][k].first]=max(dp[i|(1<<v[j][k].first)][v[j][k].first],dp[i][j]+v[j][k].second);
				for(int k=((1<<n)-1-i)|(1<<j);k;k=(k-1)&(((1<<n)-1-i)|(1<<j)))
					if(k&(1<<j))
						dp[i|k][j]=max(dp[i|k][j],dp[i][j]+b[k]);
			}
	cout<<ans-dp[(1<<n)-1][n-1];
}