#include <fstream>
#define NMAX 19
#define INF 1<<30
using namespace std;
ifstream  fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,v[NMAX][NMAX],dp[1<<NMAX][NMAX];

void citire()
{
    fin>>n>>m;

    int a,b,c;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        v[a][b]=c;
    }
}

int main()
{
    citire();

    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
        {
            dp[i][j]=INF;
        }
    }

    dp[1][0]=0;
    for(int masca=1; masca<(1<<n); masca++)
    {
        for(int i=0; i<n; i++)
        {
            if(masca&(1<<i))
            {
                for(int j=0; j<n; j++)
                {
                    if(v[i][j] && (!(masca&(1<<j))))
                    {
                        dp[masca|(1<<j)][j]=min(dp[masca|(1<<j)][j],dp[masca][i]+v[i][j]);
                    }
                }
            }
        }
    }

    int ans=INF;
    for(int i=1; i<n; i++)
    {
        if(v[i][0])
        {
             ans=min(ans,dp[(1<<n)-1][i]+v[i][0]);
        }
    }

    if(ans==INF)
    {
        fout<< "Nu exista solutie";
    }
    else
    {
        fout<< ans;
    }
    fout<< "\n";

    return 0;
}