#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Rep(i,a,b) for (int i=b;i>=a;i--)
using namespace std;
int n,m,mp[16][16],x,y,z,mmh[1<<15][15],o[1<<15][15];
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline int work(int a,int b)
{
    int mmh=0;
    for (int i=0;i<n;i++)
    if ((a>>i)&1) mmh+=o[b][i];
    return mmh;
}
int main()
{
    n=read();m=read();
    memset(mp,0,sizeof(mp));
    memset(mmh,63,sizeof(mmh));
    while(m--)
	{
        x=read();y=read();z=read();
		x--;y--;
        mp[x][y]=mp[y][x]=z;
    }
    For(i,0,(1<<n)-1)
	    For(j,0,n-1)
		{
	        o[i][j]=0;
	        For(k,0,n-1)if ((i>>k)&1) o[i][j]+=mp[j][k];
	    }
    mmh[1][0]=0;
    For(i,0,(1<<n)-1)
	    For(j,0,n-1)
		    if ((i>>j)&1){
		        For(k,0,n-1)
		       		if (mp[j][k])
		        		if (!((i>>k)&1)) 
							mmh[i|(1<<k)][k]=min(mmh[i|(1<<k)][k],mmh[i][j]+work(i,1<<k)-mp[j][k]);
		        int u=(1<<n)-1-i;
		        for (int p=u;p;p=(p-1)&u) mmh[i|p][j]=min(mmh[i|p][j],mmh[i][j]+work(i^(1<<j),p));
		    }
    printf("%d\n",mmh[(1<<n)-1][n-1]);
}