P3959

#include<bits/stdc++.h>
using namespace std;
namespace IO {
	char buf[50];
}
inline void qr(int &x){char ch=getchar(),lst=' ';while(ch>'9'||ch<'0')lst=ch,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if (lst=='-')x=-x;}
inline void write(int x,const char aft,const bool pt){if(x<0){putchar('-');x=-x;}int top=0;do{IO::buf[++top]=x%10+'0';x/=10;} while(x);while(top)putchar(IO::buf[top--]);if(pt)putchar(aft);}
const int maxt=1<<15;
const int INF=0x3f3f3f3f;
int n,m,a,b,c,ans=INF;
int f[maxt][15],g[maxt],dis[15][15];
int main(){
	qr(n);qr(m);
	memset(dis,0x3f,sizeof dis);
	for(register int i=1;i<=m;++i){
		a=b=c=0;qr(a);qr(b);qr(c);--a;--b;
		dis[b][a]=dis[a][b]=min(dis[a][b],c);
	}
	memset(f,0x3f,sizeof f);
	int all=(1<<n)-1;
	for(register int i=1;i<=all;++i){
		for(register int j=0;j<n;++j)if(((1<<j)|i)==i){
			dis[j][j]=0;
			for(register int k=0;k<n;++k)if(dis[j][k]!=INF){
				g[i]|=(1<<k);
			}
		}
	}
	for(register int i=0;i<n;++i)f[1<<i][0]=0;
	for(register int i=2;i<=all;++i){
		for(register int s0=i-1;s0;s0=(s0-1)&i)if((g[s0]|i)==g[s0]){
			int sum=0;
			int ss=s0^i;
			for(register int k=0;k<n;++k)if((1<<k)&ss){
				int temp=INF;
				for(register int h=0;h<n;++h)if((1<<h)&s0){
					temp=min(temp,dis[h][k]);
				}
				sum+=temp;
			}
			for(register int j=1;j<n;++j)if(f[s0][j-1]!=INF){
				f[i][j]=min(f[i][j],f[s0][j-1]+sum*j);
			}
		}
	}
	for(register int i=0;i<n;++i)ans=min(ans,f[all][i]);
	write(ans,'\n',true);
	return 0;
}