#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,d[15][15];
struct S{
	int dep[15],p;
	S(){
		memset(dep,-1,sizeof(dep));
		p=0x3f3f3f3f;
	}
}f[10005][15];
int cnt(int x){
	int rt=0;
	while(x){
		if(x%2) rt++;
		x=x>>1;
	}
	return rt;
}
int s(int x){
	int rt=0;
	while(x){
		rt++;
		x=x>>1;
	}
	return rt;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(d,0x3f,sizeof(d));
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		d[x][y]=d[y][x]=min(d[x][y],z);
	}
	for(int i=1;i<=n;i++) f[1<<(i-1)][1].p=0,f[1<<(i-1)][1].dep[i]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<1<<n;j++)
			for(int k=1;k<1<<n;k++){
				if(k<j||cnt(k-j)!=1||cnt(k)!=i||f[j][i-1].p==0x3f3f3f3f) continue;
				int minn=2147483647,minid,t=0,u=s(k-j);
				for(int o=1;o<=n;o++)
					if(f[j][i-1].dep[o]!=-1&&d[u][o]!=0x3f3f3f3f&&minn>d[u][o]*f[j][i-1].dep[o]){
						minn=d[u][o]*f[j][i-1].dep[o];
						minid=o;
					}
				if(f[k][i].p>f[j][i-1].p+minn){
					f[k][i].p=f[j][i-1].p+minn;
					for(int o=1;o<=n;o++) f[k][i].dep[o]=f[j][i-1].dep[o];
					f[k][i].dep[u]=f[j][i-1].dep[minid]+1;
				}
			}
	}
	printf("%d",f[(1<<n)-1][n].p);
	return 0;
}