#include<bits/stdc++.h>
namespace my_std {
	using namespace std;
#define reg register
#define Rint register int
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
#define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)+1;++i)
#define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)-1;--i)
#define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
#define MEM(x,v) memset(x,v,sizeof(x))
#define fir first
#define sec second
#define pq priority_queue
#define PII pair<int,int>
#define MP make_pair
	typedef long long LL;
	typedef double DB;
#define Templ(T) template<typename T>
	inline int read() {
		int ans=0,f=1;
		char c=getchar();
		while(!isdigit(c)) {
			f^=(c=='-');
			c=getchar();
		}
		for(; isdigit(c); c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48);
		return f?ans:-ans;
	}
	Templ(_Tp) inline int chkmin(_Tp &x,_Tp y) {
		return x>y?x=y,1:0;
	}
	Templ(_Tp) inline int chkmax(_Tp &x,_Tp y) {
		return x<y?x=y,1:0;
	}
#define using_mod
	const int mod = 998244353 , N = 18;
#ifdef using_mod
	inline void inc(int &x,const int &y) {
		x+=y;
		if(x>=mod) x-=mod;
	}
	inline int ksm(int x,LL y) {
		int res=1;
		for(; y; y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
		return res;
	}
#endif
	Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y) {
		return y?gcd(y,x%y):x;
	}
#define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
}
using namespace my_std;
#define inf (1145141919)
int n,a[N][N],m,f[60010],g[60010],h1[60010],hN[60010],P[60010];
//f[sta] : 连通块 sta 最少删权值和多少的边成为树
//g[sta] : 块 sta 所有向外的边的权值和
//h1[sta] , hN[sta] : 块 sta 所有连向 1/N 的边权值和
//PP(sta1,sta2) : 块 sta1 和 sta2 互相连边的权值和
inline int Count_(int sta,vector<int> &vec) {
	Rint t = 0,res = 0;
	while(sta) {
		if(sta & 1) ++res , vec.push_back(t);
		++t , sta >>= 1;
	}
}

inline int PP(int S1,int S2) {
	reg vector<int> vec1,vec2;
	Rint res = 0;
	Count_(S1,vec1) , Count_(S2,vec2);
	for(auto x1 : vec1) {
		for(auto x2 : vec2) if(a[x1][x2] != inf) res += a[x1][x2];
	}
	return res;
}

int main() {
	n = read() , m = read();
	FOR(i,0,n) FOR(j,0,n) a[i][j] = inf;
	Rint u,v;
	FOR(i,1,m) u = read() - 1 , v = read() - 1 , a[u][v] = a[v][u] = read();
	FOR(i,0,(1 << n) - 1) f[i] = inf;
//	FOR(i,0,n - 1){ FOR(j,0,n - 1) printf("%d ",a[i][j]); puts(""); }
//	FOR(i,0,n - 1) f[1 << (i)] = 0;
	FOR(sta,1,(1 << n) - 1) {
		Rint cnt;
		vector<int> vec;
		cnt = Count_(sta,vec);
		Rint res,sum;
		for(auto x : vec) {
			res = inf , sum = 0;
			for(auto v : vec) { //找出最大的边
				chkmin(res,a[x][v]);
				if(a[x][v] != inf) sum += a[x][v];
			}
			chkmin(f[sta] , f[sta ^ (1 << x)] + sum - res);
			FOR(i,0,n - 1) if(!(sta & (1 << i)) && a[x][i] != inf) g[sta] += a[x][i];
			if(!(sta & 1) && a[x][1] != inf)  h1[sta] += a[x][1];
			if(!(sta & (1<<(n-1))) && a[x][n-1] != inf)  hN[sta] += a[x][n-1];
		}
		//get f[sta] , g[sta] , h1[sta] , hN[sta]
	}
//	FOR(sta,1,(1 << n) - 1) printf("%d : %d , %d , %d , %d\n",sta,f[sta],g[sta],h1[sta],hN[sta]);
	FOR(sta,1,(1 << n) - 1) {
		Rint cnt;
		vector<int> vec;
		cnt = Count_(sta,vec);
		P[sta] = inf;
		for(Rint S = (sta - 1) & sta,T; S; S = (S - 1) & sta) {
			T = sta ^ S;
			chkmin(P[sta],g[S] + g[T] - h1[S] - hN[T] - PP(S,T));
		}
	}
	Rint ans = 1145141919;
	FOR(sta,1,(1 << n) - 1) {
		if(f[sta] >= 0 && P[sta ^ ((1 << n) - 1)] >= 0) chkmin(ans,f[sta] + P[sta ^ ((1 << n) - 1)]);
	}
	printf("%d\n",ans);
	return 0;
}