#include <iostream>
#include<fstream>
using namespace std;ifstream fin("hamilton.in");ofstream fout("hamilton.out");
int dp[1<<18][19],dst[19][19],n,m,a,b,k,msk,bit,bit2,i,j,rsp=1e9;
int main()
{
   fin>>n>>m;for(i=0;i<=n;i++)for(j=0;j<=n;j++)dst[i][j]=1e9;
   for(i=1;i<=m;i++){fin>>a>>b>>k;dst[a][b]=k;}
   for(i=0;i<(1<<n);i++)for(j=0;j<=n;j++)dp[i][j]=1e9;dp[1][0]=0;
   for(msk=1;msk<(1<<n);msk++){
    for(bit=0;bit<n;bit++)if(msk&(1<<bit)){
        int new_mask=msk^(1<<bit);
        for(bit2=0;bit2<n;bit2++){
            if((new_mask&(1<<bit2))&&bit2!=bit)
                dp[msk][bit]=min(dp[msk][bit],dp[new_mask][bit2]+dst[bit2][bit]);
        }
    }
   }
   for(i=1;i<n;i++)rsp=min(rsp,dp[(1<<n)-1][i]+dst[i][0]);if(rsp==1e9)fout<<"Nu exista solutie";else fout<<rsp;
    return 0;
}