#include <fstream>
using namespace std;
ifstream f("hamilton.in");ofstream g("hamilton.out");
#define LE 300666
#define inf 1<<30
int dp[LE][19],n,m,i,j;
int xx,yy,cc,a[66][66],result=inf;
int bit;

int main(){
   f>>n>>m;
   for(i=1;i<=m;++i){f>>xx>>yy>>cc;a[xx][yy]=cc;}

   for(i=0;i<=(1<<n);++i)
     for(j=0;j<=n;++j) dp[i][j]=inf;
   dp[1][0]=0;

  for(i=1;i<(1<<n);++i)
    for(j=0;j<=n;++j) if (dp[i][j]<inf)
      for(bit=0;bit<n;++bit)
        if ((i&(1<<bit))==0&&a[j][bit]>0)
          if (dp[i|(1<<bit)][bit]>dp[i][j]+a[j][bit])
            dp[i|(1<<bit)][bit]=dp[i][j]+a[j][bit];

  for(j=0;j<n;++j)
    if (a[j][0])
      result=min(a[j][0]+dp[i-1][j],result);

   g<<result<<'\n';
   f.close();g.close();
    return 0;
}