#include <fstream>

using namespace std;

ifstream F("hamilton.in");
ofstream G("hamilton.out");

int n, m, x, y, z, L, sol, c[262150][20], cost[20][20];
const int inf = 1e9;

int main()
{
    F >> n >> m;
    for( int i = 1; i <= m; ++ i )
    {
        F >> x >> y >> z;
        cost[x][y] = z;
    }
    L = 1 << n;
    for( int i = 0; i < L; ++ i )
        for( int j = 0; j < n; ++ j ) c[i][j] = inf;
    c[1][0] = 0;
    for( int i = 1; i < L; ++ i )
        for( int j = 0; j < n; ++ j )
            if( i & (1<<j) )
            {
                for( int k = 0; k < n; ++ k )
                    if( j != k && i &(1<<k) && cost[k][j] )
                        c[i][j] = min(c[i][j], c[i^(1<<j)][k] + cost[k][j]);
            }
    sol = inf;
    for( int k = 0; k < n; ++ k )
        if(cost[k][0]) sol = min(sol, c[L-1][k] + cost[k][0]);
    if(sol==inf) G << "Nu exista solutie";
    else G << sol;
    return 0;
}