#include <fstream>
#include <vector>

using namespace std ;

const int MAXN = 20 ;
const int MAXX = 262150 ;
const int INF = 100000000 ;

int N , M , Sol ;
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];
vector <int> A[MAXN];

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    fin >> N >> M;

    for ( int i = 0 ; i < N ; ++ i )
        for ( int j = 0 ; j < N ; ++ j )
                    Cost[i][j] = INF;

    for ( int i = 1 ; i <= M ; ++ i )
    {
        int x , y ;

        fin >> x >> y ;
        A[y].push_back(x) ;
        fin >> Cost[x][y] ;
    }

    for ( int i = 0 ; i < 1 << N ; ++ i )
        for ( int j = 0 ; j < N ; ++ j )
                C[i][j] = INF ;

    C[1][0] = 0 ;

    for ( int i = 0 ; i < 1 << N ; ++ i )
        for ( int j = 0 ; j < N ; ++j )
            if ( i & ( 1 << j ) )
                for ( unsigned int k = 0 ; k < A[j].size() ; ++ k )
                    if ( i & ( 1 << A[j][k] ) )
                        C[i][j] = min ( C[i][j] , C [ i ^ ( 1 << j ) ] [ A[j][k] ] + Cost[ A[j][k] ][j] ) ;

    Sol = INF ;
    for ( unsigned int i = 0 ; i < A[0].size() ; ++ i )
        Sol = min ( Sol , C[ ( 1 << N ) - 1 ][ A[0][i] ] + Cost[ A[0][i] ][0] ) ;

    if ( Sol == INF )
         fout << "Nu exista solutie" << endl;
    else fout << Sol << endl;

    return 0;
}