#include<cstdio>
#include<vector>
#define INF 2000000000
using namespace std;
vector< pair< int , int  > >L[30];
int n,m,i,j,k,a,b,c,vmin,v[30],x[20][300100];
FILE *f,*g;
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
int main(){
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&c);
        L[a].push_back( make_pair(b,c) );
    }
    for(i=0;i<n;i++){
        for(j=1; j <= ( 1 << n ); j++){
            x[i][j] = INF;
        }
    }
    x[0][1] = 0;
    for( i = 3 ; i <= ( 1 << n ) ; i += 2 ){
        for(j=0; j<n; j ++){
            if( i & ( 1 << j ) ){
                for( k = 0; k < L[j].size(); k++ ){
                    a = L[j][k].first;
                    b = L[j][k].second;
                    if( ( i & ( 1 << a ) ) && x[j][i] > x[a][ ( i - ( 1 << j ) ) ] + b ){
                        x[j][i] = x[a][ ( i - ( 1 << j ) ) ] + b;
                    }
                }
            }
        }
    }
    vmin = INF;
    for( i = 0; i < L[0].size() ; i++ ){
        vmin = minim( vmin , x[ L[0][i].first ][ ( 1 <<  n ) - 1 ] + L[0][i].second );
    }
    if( vmin != INF )
        fprintf(g,"%d",vmin);
    else
        fprintf(g,"Nu exista solutie");




    fclose(f);
    fclose(g);
    return 0;
}