#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

int n, m, x, y, c, cost[ 18 ][ 18 ], d[ 1 << 18 ][ 20 ];
vector < int > v[ 20 ];
const int inf = 1 << 25;

int hamilton( int mask, int ep )
{
    int x;
    if ( d[ mask ][ ep ] == inf )
    {
        d[ mask ][ ep ] = -1;

        for ( int i = 0; i < (int)v[ ep ].size(); ++ i )
        {
            x = v[ ep ][ i ];
            if ( !x && (1 << ep) + 1 != mask )continue;
            if ( mask && (1 << x) )
            {
                d[ mask ][ ep ] = min( hamilton( mask ^ (1 << ep), x ) + cost[ x ][ ep ], d[ mask ][ ep ] );
            }
        }
    }
    return d[ mask ][ ep ];
}

int main()
{
    f >> 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 )
    {
        f >> x >> y >> c;
        cost[ x ][ y ] = c;
        v[ y ].push_back( x );
    }

    memset( d, -1, sizeof( d ) );
    d[ 1 ][ 0 ] = 0;

    int r = inf;
    for ( int i = 1; i <= n; ++ i )
    {
        if ( cost[ i ][ 0 ] != inf ) r = min( r, hamilton( (1 << n) - 1, i ) + cost[ i ][ 0 ] );
        if ( r == inf ) g << "Nu exista solutie";
        else g << r;
    }
    return 0;
}