#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct edge{
	int k,w,next;
}e[1005];
int n,m,f[20][20][100005],home[20],cnt=-1,E[1000005][3],tot=0;
bool vis[20][20][100005];
void add(int x,int y,int w){
	cnt++;
	e[cnt].k=y;
	e[cnt].w=w;
	e[cnt].next=home[x];
	home[x]=cnt;
}
void dfs(int S,int s,int t){
	if(vis[s][t][S]) return;
	vis[s][t][S]=vis[t][s][S]=1;
	if(s==t) return;
	f[s][t][S]=1e9;
	int L=tot+1,R;
	for(int i=1;i<=n;i++)if(S&(1<<i-1)){
		for(int p=home[i];~p;p=e[p].next) if(i<e[p].k&&(S&(1<<e[p].k-1))) E[++tot][0]=e[p].k,E[tot][1]=i,E[tot][2]=e[p].w;
	}
	R=tot;
	for(int i=(S-1)&S;i;i=(i-1)&S)if((i&(1<<s-1))&&!(i&(1<<t-1))){
		int x=S^i,sum=0;
		for(int p=L;p<=R;p++)if(((i>>E[p][0]-1)&1)==((x>>E[p][1]-1)&1)){
			sum+=E[p][2];
		}
		for(int p=L;p<=R;p++)if(((i>>E[p][0]-1)&1)==((x>>E[p][1]-1)&1)&&f[s][t][S]>sum-E[p][2]){
			int xx=E[p][0],yy=E[p][1];
			if(!(i&(1<<xx-1))) swap(xx,yy);
			dfs(i,s,xx);
			dfs(x,yy,t);
			f[s][t][S]=min(f[s][t][S],f[s][xx][i]+f[yy][t][x]+sum-E[p][2]);
			if(f[s][t][S]<0){
				cout<<"";
			}
		}
	}
	tot=L-1;
	f[t][s][S]=f[s][t][S];
}
int main(){
	memset(home,-1,sizeof(home));
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,w;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);add(y,x,w);
	}
	dfs((1<<n)-1,1,n);
	printf("%d",f[1][n][(1<<n)-1]);
	return 0;
}