#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=13,M=4096,INF=0x01010101;
int a[N][N],f[M][M],g[N][M],ne[M],lg[M];
inline void chkmn(R&x,R y){
	if(x>y)x=y;
}
int main(){
	memset(a,1,sizeof(a));
	memset(g,63,sizeof(g));//貌似需要区别对待
	R n,m,S,s,i,j,l,x,y,v;
	cin>>n>>m;
	S=(1<<n)-1;
	for(i=0;i<n;++i)
		lg[1<<i]=i;//log预处理
	while(m--){
		cin>>x>>y>>v;
		if(a[--x][--y]>v)//邻接矩阵存边
			a[x][y]=a[y][x]=v;
	}
	for(i=1;i<=S;++i){
		v=0;
		for(j=s=S^i;j;j=(j-1)&s)
			ne[j]=v,v=j;//为了更新顺序需要反向枚举
		for(j=v;j;j=ne[j]){
			x=lg[j&-j];v=INF;
			for(y=0;y<n;++y)//找到可以连接的最小边权
				if(1<<y&i)chkmn(v,a[x][y]);
			f[i][j]=f[i][j^(j&-j)]+v;
		}
	}
	for(i=1;i<=S;i<<=1)
		g[0][i]=0;//状态预处理
	for(l=1;l<n;++l)
		for(i=1;i<=S;++i)
			for(j=i;j;j=(j-1)&i)
				chkmn(g[l][i],g[l-1][i^j]+f[i^j][j]*l);
	v=0x7fffffff;
	for(l=0;l<=n;++l)
		chkmn(v,g[l][S]);
	cout<<v<<endl;
	return 0;
}