/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];
int sum[1<<N];
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){
	for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
	cin>>n>>m;
	int tot=0;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		tb[x][y]=tb[y][x]=z;
		tot+=z;
	}
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
			sum[i]+=tb[j][k];
//		printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
	}
	for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;
	int mx=-inf;
	for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){
		if(j)
			for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){
				dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);
				if(!k)break;
			}
		else
			dp[i][j]=sum[i];
//		printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
		for(int k=0;k<n;k++)if(!(i&1<<k))
			if(tb[j][k])
				tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
	}
	cout<<tot-dp[(1<<n)-1][n-1];
	return 0;
}
/*1
4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100
*/
/*2
2 1
1 2 1
*/
/*3
15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491
*/
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];
int sum[1<<N];
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){
	for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
	cin>>n>>m;
	int tot=0;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		tb[x][y]=tb[y][x]=z;
		tot+=z;
	}
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
			sum[i]+=tb[j][k];
//		printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
	}
	for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;
	int mx=-inf;
	for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){
		if(j)
			for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){
				dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);
				if(!k)break;
			}
		else
			dp[i][j]=sum[i];
//		printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
		if(j==n-1)mx=max(mx,dp[i][j]);
		for(int k=0;k<n;k++)if(!(i&1<<k))
			if(tb[j][k])
				tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
	}
	cout<<tot-mx;
	return 0;
}
/*1
4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100
*/
/*2
2 1
1 2 1
*/
/*3
15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491
*/