#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 5000

 #define inf (0X7f7f7f7f)

 using namespace std;

 int n,m,ans=2e9,f[N],dis[],w[N][N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 void dfs(int x){

     for(rg int i=;i<=n;i++)if(<<(i-)&x)

         for(rg int j=;j<=n;j++)if(w[i][j]!=inf&&(<<(j-)&x)==)

             if(f[x|(<<(j-))]>f[x]+dis[i]*w[i][j]){

                 int d=dis[j];

                 dis[j]=dis[i]+;

                 f[x|(<<(j-))]=f[x]+dis[i]*w[i][j];

                 dfs(x|(<<(j-)));

                 dis[j]=d;

             }

 }

 int main(){

     n=read(); m=read();

     memset(w,inf,sizeof(w));

     for(rg int i=;i<=m;i++){

         int u=read(),v=read(),d=read();

         w[u][v]=w[v][u]=min(w[u][v],d);

     }

     for(rg int i=;i<=n;i++){

         memset(f,inf,sizeof(f));

         memset(dis,inf,sizeof(dis));

         dis[i]=; f[<<(i-)]=;

         dfs(<<(i-));

         ans=min(ans,f[(<<n)-]);

     }

     printf("%d\n",ans);

     return ;

 }