#include <cstdio>
#include <vector>

#define rint register int
#define pb push_back

const char IN[] = "hamilton.in";
const char OUT[] = "hamilton.out";
const int MAX = 20;
const int BITMAX = 263000;
const int INF = 1<<30;

using namespace std;

int cost[MAX][MAX];
int d[BITMAX][MAX];
vector <int> gr[MAX];

inline int min(int a,int b){
    if(a>b)return b;
    return a;
}

int main()
{
    int n,m;
    freopen( IN , "r" , stdin );
    freopen( OUT , "w" , stdout );
    scanf( "%d %d" , &n , &m);
    for( rint i = 0 ; i < n ; ++ i )
        for( rint j = 0 ; j < n ; ++ j )
            cost[i][j]=INF;
    while( m-- ){
        int x,y;
        scanf( "%d %d" , &x , &y );
        gr[y].pb(x);
        scanf("%d",&cost[x][y]);
    }
    for( rint i = 0 ; i < (1 << n) ; ++ i )
        for( rint j = 0 ; j <= n ; ++ j )
            d[i][j]=INF;
    d[1][0]=0;
    for( rint i = 0 ; i < (1 << n) ; ++ i )
        for( rint j = 0 ; j < n ; ++ j )
            if( i & (1<<j) ){
                for( rint k = 0 ; k < (int)gr[j].size( ) ; ++ k )
                    if( i & (1<<gr[j][k]) ){
                        d[i][j]=min(d[i][j],d[ i ^ (1<<j) ][gr[j][k]]+ cost[gr[j][k]][j] );
                    }
            }
    int sol=INF;
    for(rint i = 0 ; i < (int)gr[0].size( ) ; ++ i ){
        sol=min( sol , d[(1<<n)-1][gr[0][i]] + cost[gr[0][i]][0] );
    }
    if(sol == INF)
        printf("Nu exista solutie\n");
    else printf("%d\n",sol);
    return 0;
}