#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-1)));mask++)
    {
        for(int j=0;j<(n-1);j++)
        {
            dp[mask][j+1]=inf;
            if((mask&(1<<j))!=0)
            {
                int prev=mask-(1<<j);
                if(prev==0)
                {
                    if(v[0][j+1]>0) dp[mask][j+1]=v[0][j+1];
                    else dp[mask][j+1]=inf;
                    ///cout<<dp[mask][j+1]<<' '<<mask<<' '<<j<<'\n';
                    continue;
                }
                for(int k=0;k<(n-1);k++)
                {
                    if((prev&(1<<k))!=0)
                    {
                        if(v[k+1][j+1]>0) dp[mask][j+1]=min(dp[mask][j+1],dp[prev][k+1]+v[k+1][j+1]);
                    }
                }
            }
            ///cout<<dp[mask][j+1]<<' '<<mask<<' '<<j<<'\n';
        }
    }
    int sol=inf;
    for(int j=1;j<n;j++)
    {
        if(v[j][0]>0)
        {
            sol=min(sol,v[j][0]+dp[(1<<(n-1))-1][j]);
        }
    }
    if(sol!=inf) fout<<sol<<'\n';
    else fout<<"Nu exista solutie"<<'\n';
    return 0;
}