#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=17;
const int INF=0x3f3f3f3f;
ll n,m,conn[MAX][MAX],dist[MAX][MAX],dp[MAX][1<<MAX],visit[MAX][1<<MAX],calc[1<<MAX],trk[MAX],ans;
void calc_build(ll x,ll v,ll idx){
    //printf("%lld %lld %lld\n",x,v,idx);
    if(idx>=n) {
        calc[x]=v;
        return;
    }
    calc_build(x,v,idx+1);
    trk[idx]=1;
    for(ll i=0;i<idx;i++) if(trk[i]) v+=dist[i][idx];
    calc_build(x+(1<<idx),v,idx+1);
    trk[idx]=0;
}
ll dp_build(ll x,ll bit){
    if(x==n-1) return dp[x][bit]=calc[bit];
    if(visit[x][bit]==0){
        visit[x][bit]=1;
        dp[x][bit]=-INF;
        for(ll i=0;i<n;i++) if(((1<<i)&bit)&&conn[i][x]){
            ll cmp[MAX],cmp_cnt=0;
            for(ll j=0;j<n-1;j++) if(((1<<j)&bit)&&i!=j&&x!=j) cmp[cmp_cnt++]=j;
            for(ll j=0;j<(1<<(cmp_cnt));j++){
                ll g1=1<<x,g2;
                for(ll k=0;k<cmp_cnt;k++) if((1<<k)&j) g1+=(1<<cmp[k]);
                g2=bit-g1;
                dp[x][bit]=max(dp[x][bit],calc[g1]+dp_build(i,g2)+dist[x][i]);
            }
        }
    }
    return dp[x][bit];
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=0;i<m;i++){
        ll t1,t2,t;
        scanf("%lld%lld%lld",&t1,&t2,&t);
        t1--,t2--;
        conn[t1][t2]=1,dist[t1][t2]=t;
        conn[t2][t1]=1,dist[t2][t1]=t;
        ans+=t;
    }
    calc_build(0,0,0);
    printf("%lld\n",ans-dp_build(0,(1<<n)-1));
}

#include <bits/stdc++.h>
#define N 20
#define M (1 << 15 | 5)
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?x:-x;
}
int mp[N][N], inc[M], cot[M][N], dp[M][N];
int main(int argc, char const *argv[]) {
	int n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int x = read() - 1, y = read() - 1;
		mp[x][y] = mp[y][x] = read();
	}
	int tot = 1 << n;
	for (int i = 0; i < tot; i++)
		for (int a = 0; a < n; a++) if (i >> a & 1)
			for (int b = 0; b < a; b++) if (i >> b & 1)
				if (mp[a][b]) inc[i] += mp[a][b];
	for (int i = 0; i < tot; i++)
		for (int a = 0; a < n; a++) if (~ i >> a & 1)
			for (int b = 0; b < n; b++) if (i >> b & 1)
				if (mp[a][b]) cot[i][a] += mp[a][b];
	memset(dp, -1, sizeof dp);
	dp[1][0] = 0;
	for (int i = 0; i < tot; i++) {
		for (int a = 0; a < n; a++) {
			if ((i >> a & 1) && ~ dp[i][a]) {
				for (int b = 0; b < n; b++) if (~ i >> b & 1)
					if (mp[a][b]) dp[i | (1 << b)][b] = max(dp[i | (1 << b)][b], dp[i][a] + mp[a][b]);
				int lst = tot - 1 - i;
				for (int j = lst; j; j = (j - 1) & lst) {
					int now = inc[j] + cot[j][a];
					dp[i | j][a] = max(dp[i | j][a], dp[i][a] + now);
				}
			}
		}
	}
	printf("%d\n", inc[tot - 1] - dp[tot - 1][n - 1]);
	return 0;
}
