#include <fstream>

#define infinite 400000000

using namespace std;

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

int n, m;

int ans, adj[20][20], DP[262150][18];

int bit[20];

int bkt ( int l, int prev, int cost, int mask ) {

    if ( DP[mask][prev] )
        return DP[mask][prev];

    if ( l >= n ) {
        if ( adj[prev][0] )
            return cost + adj[prev][0];
    }

    int res = infinite;
    for ( int i = 1; i < n; i++ ) {

        if ( !( mask & bit[i] ) && adj[ prev ][ i ] ) {

            int aux = bkt ( l+1, i, cost + adj[prev][i], mask | bit[i] );
            res = min ( aux, infinite );
        }
    }

    DP[mask][prev] = res;
    return DP[mask][prev];
}

void init () {

    int aux = 1;
    for ( int i = 0; i < 18; i++ ) {
        bit[i] = aux << i;
    }
}

void solve () {

    init();
    ans = bkt ( 1, 0, 0, 0);

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

void read () {

    fin >> n >> m;

    int from, to, cost;
    for ( int i = 1; i <= m; i++ ) {

        fin >> from >> to >> cost;
        adj[ from ][ to ] = cost;
        //adj[ to ][ from ] = cost;
    }
}

int main()
{
    read ();
    solve ();
    return 0;
}