#include <bits/stdc++.h>
#define N 18
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[N][1<<N],n,m,a[N][N];
int main()
{
    int x,y,i,j,mask;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>mask;
        a[x][y]=mask;
    }
    int P=1<<n;
    for(i=0;i<n;i++)
        fill(dp[i],dp[i]+P,2e9);
    dp[0][1]=0;
    for(mask=3;mask<P;mask+=2)
        for(i=1;i<n;i++)
          if(mask&(1<<i))
            for(j=0;j<n;j++)
              if((mask&(1<<j)) && a[j][i])
                dp[i][mask]=min(dp[i][mask],dp[j][mask^(1<<i)]+a[j][i]);
    int sol=2e9;
    for(i=1;i<n;i++)
        if(a[i][0]) sol=min(sol,dp[i][P-1]+a[i][0]);
    if(sol==2e9) fout<<"Nu exista solutie";
    else fout<<sol;
    return 0;
}