#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define N 19
#define INF 2000000000

using namespace std;

vector < int >muc[N];
vector < int >::iterator it;
int c[N][N];
int d[1<<N][N];
int n,sol;

void printmat(){
    static int i,j;

    for(i=0;i<1<<n;i++){
        for(j=0;j<n;j++){
            printf("%5d ",d[i][j]);
        }
        printf("\n");
    }
    printf("\n");

}

int main(){
    int m,i,j;
    int x,y,cost;

    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=0;i<(1<<n);i++){
        for(j=0;j<n;j++){
            d[i][j]=c[i][j]=INF;
        }
    }

    for(i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&cost);

        muc[y].push_back( x);
        c[x][y]=cost;
    }

//
//    for(i=1;i<n;i++ ){
//        d[i][0] = c[i][0];
//
//    }
    d[1][0]=0;

    for(i=0; i<=1<<n;i++){
        for(j=0;j<n;j++){
            if( ! i&(1<<n) ){
                continue;
            }
            for(it=muc[j].begin() ; it!=muc[j].end();it++ ){
                if( i&(1<<*it) ){
                    d[i][j]=min( d[i][j], d[i^(1<<j)][*it]+c[*it][j] );
                }
            }
        }
    }

   // printmat();

    sol=INF;

    for(it=muc[0].begin(); it!=muc[0].end();it++ ){
        sol=min(sol, d[(1<<n)-1][*it] + c[*it][0] )    ;
    }

    if(sol==INF){
        printf("Nu exista solutie");
    }else{
        printf("%d",sol);
    }
    return 0;
}