#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int Nmax=20,inf=2e9;
int v[Nmax][Nmax];
int dp[(1<<Nmax)][Nmax];
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        v[x][y]=c;
    }
    for(int mask=0;mask<(1<<n);mask++)
    {
        for(int j=0;j<n;j++)
        {
            dp[mask][j]=inf;
            if((mask&(1<<j))!=0)
            {
                int prev=mask-(1<<j);
                if(prev==0)
                {
                    dp[mask][j]=0;
                    //cout<<dp[mask][j]<<' '<<mask<<' '<<j<<'\n';
                    continue;
                }
                for(int k=0;k<n;k++)
                {
                    if((prev&(1<<k))!=0)
                    {
                        if(v[k][j]>0) dp[mask][j]=min(dp[mask][j],dp[prev][k]+v[k][j]);
                    }
                }
            }
            ///cout<<dp[mask][j]<<' '<<mask<<' '<<j<<'\n';
        }
    }
    int sol=inf;
    for(int j=0;j<n;j++)
    {
        if(v[j][0]>0)
        {
            sol=min(sol,v[j][0]+dp[(1<<n)-1][j]);
        }
    }
    if(sol!=inf) fout<<sol<<'\n';
    else fout<<"Nu exista solutie"<<'\n';
    return 0;
}