in:
5 4
1 2 3
1 3 3
1 4 3
1 5 3

out:
12

#include<bits/stdc++.h>
const int M(1<<12|1),N(13),EDGE(1011),INF(20050305);
using namespace std;
int n,m;
int dis[N][N];
namespace bit{
	inline int count(int k){
		int ans(0);
		while(k){
			ans+=k&1;
			k>>=1;
		}
		return ans;
	}
	inline bool get(int k,int p){                           //从右往左p位 
		return k&(1<<p-1);
	}
	inline int to(int k,int p){
		return k&~(1<<p-1);
	}
	inline int add(int x,int y){
		while(!!y){
			int t(x);
			x^=y;
			y=(x&y)<<1;
		}
	}
	inline void print_bit(int k){
		if(!k)return;
		print_bit(k>>1);
		putchar('0'+(k&1));
	}
	inline void swap(int x,int y){
		x^=y;
		y^=x;
		x^=y;
	}
	inline int fan(int k){
		return k^(1<<n)-1;
	}
}
namespace get_in{
	inline int read( ){
		int sum(0);
		char ch(getchar( ));
		while(ch==' '||ch=='\n')ch=getchar( );
		while(ch>='0'&&ch<='9'){
			sum=(sum<<1)+(sum<<3)+ch-'0';
			ch=getchar( );
		}
		return sum;
	}
}
using namespace get_in;
using namespace bit;
int t[N][N];
int len[N];
inline void pre( ){
	int i,j,k;
	n=read( );m=read( );
	for(i=1;i<=n;++i){
		for(j=1;j<=n;++j){
			dis[i][j]=INF;
		}
		dis[i][i]=0;
	}
	while(m--){
		int x(read( )),y(read( )),z(read( ));
		if(z>dis[x][y])continue;
		if(dis[x][y]==INF){
			t[x][++len[x]]=y;
			t[y][++len[y]]=x;
		}
		dis[x][y]=dis[y][x]=z;
	}
	
}
int d[N],que[N];
int tep,ans(INF);
int cnt,minn,nod;
inline void dfs(int first,int k){
	if(k==n){
		ans=tep;
		return;
	}
	int i,j,x,y;
	for(x=first;x<=cnt;++x){
		if(tep+d[i]*minn>=ans)return;
		i=que[x];
		for(y=1;y<=len[i];++y)
		if(!d[j=t[i][y]]){
			tep+=d[i]*dis[i][j];
			d[j]=d[i]+1;
			que[++cnt]=j;
			minn-=dis[i][t[i][1]];
			dfs(x,k+1);
			minn+=dis[i][t[i][1]];
			--cnt;
			d[j]=0;
			tep-=d[i]*dis[i][j];
		}
	}
}
int p;
inline bool cmp(int x,int y){
	return dis[x][p]<dis[y][p];
}
signed main( ){
	pre( );
	int i;
	for(i=1;i<=n;i++){
		p=i;
		sort(t[i]+1,t[i]+1+len[i],cmp);
		minn+=dis[i][t[i][1]];
	}
	for(i=1;i<=n;i++){
		tep=0;
		fill(d+1,d+1+n,0);
		d[i]=1;
		que[cnt=1]=i;
		minn-=dis[i][t[i][1]];
		dfs(1,1);
		d[i]=0;
		minn+=dis[i][t[i][1]];
	}
	printf("%d",ans);
}