#include<bits/stdc++.h>
namespace FAST_IO{
	char buf[1<<20],*p1,*p2,ch;
	int x,f;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	inline int read(){
		x=f=0,ch=getchar();
		while(!isdigit(ch)){
			if(ch=='-')f=1;
			ch=getchar();
		}
		do x=(x<<1)+(x<<3)+(ch^48),ch=getchar();while(isdigit(ch));
		return f?-x:x;
	}
	inline void Write(register const int &p){
		if(9<p)Write((p>>1)/5);
		putchar(p%10|48);
	}
	inline void write(register const int &p,register const char c='\n'){if(p<0)putchar('-'),Write(-p);else Write(p);putchar(c);}
}
using FAST_IO::read;
using FAST_IO::write;
using namespace std;
const int M=4005,N=20;
int nxt[M],head[N],to[M],dis[M],Cnt,n,m,s,ans=1e9,w[15][15],f[15][15];
bool pd[15],tmp[15][15],vis[N];
struct node{
	int u,v,w;
}e[M];
struct Node{
	int x,y;
}p[15];
inline void add(register const int u,register const int v,register const int W){
	nxt[Cnt=-~Cnt]=head[u];
	head[u]=Cnt;
	to[Cnt]=v;
	dis[Cnt]=W;
}
inline void dfs(register const int x,register const int sum,register const int tot);
inline void pai(register const int x,register const int cnt,register const int X,register const int Sum,register int tot,register const int TOT,register const Node AA[]){
	if(x>cnt){
		if(!TOT)return;
		dfs(-~X,Sum,tot+TOT);
		return;
	}
	register const Node A(p[x]);
	pai(-~x,cnt,X,Sum,tot,TOT,AA);
	p[x]=A;
	w[X][++w[X][0]]=p[x].x;
	vis[p[x].x]=1;
	pai(-~x,cnt,X,Sum+p[x].y*(X-1),tot,TOT+1,AA);
	p[x]=A;
	vis[p[x].x]=0;
	w[X][w[X][0]]=0;
	w[X][0]--;
}
inline void dfs(register const int x,register const int sum,register const int tot){
	if(sum>=ans)return;
	if(tot==n){
		ans=sum;
		return;
	}
	register int cnt(0);
	register Node AA[15];
	memset(pd,0,sizeof(pd));
	for(register int i(1);i^(-~w[~-x][0]);i=-~i)
		for(register int j(head[w[~-x][i]]);j;j=nxt[j]){
			if(vis[to[j]])continue;
			if(!pd[to[j]])p[++cnt]={to[j],dis[j]},pd[to[j]]=cnt;
			else p[pd[to[j]]].y=min(p[pd[to[j]]].y,dis[j]);
		}
	if(!cnt)return;
	for(register int i(1);i^(-~cnt);i=-~i)
		AA[i]=p[i];
	pai(1,cnt,x,sum,tot,0,AA);
}
int main(){
//	freopen("treasure.in","r",stdin);
//	freopen("treasure.out","w",stdout);
	n=read(),m=read();
	memset(f,127,sizeof(f));
	for(register int i(1);i^(-~m);i=-~i){
		e[i].u=read(),e[i].v=read(),e[i].w=read();
		f[e[i].u][e[i].v]=f[e[i].v][e[i].u]=min(f[e[i].v][e[i].u],e[i].w);
	}
	for(register int i(1);i^(-~m);i=-~i){
		if(tmp[e[i].u][e[i].v])continue;
		tmp[e[i].u][e[i].v]=tmp[e[i].v][e[i].u]=1;
		add(e[i].u,e[i].v,f[e[i].u][e[i].v]);
		add(e[i].v,e[i].u,f[e[i].u][e[i].v]);
	}
	for(register int i(1);i^(-~n);i=-~i){
		w[1][1]=i;
		w[1][0]=1;
		vis[i]=1;
		dfs(2,0,1);
		vis[i]=0;
	}
	printf("%lld",ans);
	return 0;
}