#include <fstream>
#define f_mare 4e9
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int nmax = 18;
unsigned sol[(1<<nmax)][nmax], minim;
int c[nmax][nmax], n, m, k, i, j, x, y, z;

int main()
{
    f >> n >> m;
    while ( m-- )
    {
        f >> x >> y >> z;
        c[x][y] = z;
    }
     for( i = 1 ; i < (1<<n) ; i++ )
        for ( j = 0 ; j < n ; j++ )
        sol[i][j] = f_mare;

    sol[1][0] = 0;
    for( i = 1 ;  i < ( 1<<n ) ; i++ )
        for( j = 0 ; j < n ; j++)
        if( i&(1<<j) != 0 )
            for( k = 0 ; k < n ; k++ )
            if( k != j && ( i&(1<<k) != 0 && c[k][j] ))
               sol[i][j]= min(sol[i][j], sol[i^(1<<j)][k]+c[k][j]);

        minim = f_mare;
        for ( i = 1 ; i < n ; i++ )
            if ( c[i][0] )
            minim = min( minim, sol[(1<<n)-1][i]+c[i][0]);
        if( minim != f_mare )
        g << minim;
        else
            g << "Nu exista solutie";
    return 0;
}