#include <fstream>
#define inf 1000000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,i,j,dis[20][20],x,y,p,k,ans;
int d[300000][20];
int main()
{fin>>n>>m;
 for(i=0;i<n;i++)
    for(j=0;j<n;j++)
       {dis[i][j]=inf;
       }
 for(i=1;i<=m;i++)
    {fin>>x>>y>>p;
     dis[x][y]=p;
    }
 for(i=0;i<(1<<n);i++)
    {for(j=0;j<n;j++)
        d[i][j]=inf;
    }
 d[1][0]=0;
 for(i=0;i<(1<<n);i++)
    {for(j=0;j<n;j++)
        {if((i&(1<<j))&&d[i][j]<inf)
           {for(k=0;k<n;k++)
               {if(dis[j][k]<inf&&!(i&(1<<k))&&d[i+(1<<k)][k]>d[i][j]+dis[j][k])d[i+(1<<k)][k]=d[i][j]+dis[j][k];
               }
           }
        }
    }
    ans=inf;
 for(i=1;i<n;i++)
    {if(dis[i][0]<inf)
       {ans=min(ans,dis[i][0]+d[(1<<n)-1][i]);
       }
    }
    fout<<ans;
}