#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 18
#define INF 1000000000
using namespace std;
 
FILE*IN,*OUT;
 
int D[1<<18][MaxN],N,M,X,Y,Z,Cost[MaxN][MaxN];
int main()
{
    IN=fopen("hamilton.in","r");
    OUT=fopen("hamilton.out","w");
 
    fscanf(IN,"%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            Cost[i][j]=INF;
    for(int i=1;i<=M;i++)
    {
        fscanf(IN,"%d%d%d",&X,&Y,&Z);
        Cost[X][Y]=Z;
    }
    for(int i=0;i<(1<<N);i++)
        for(int j=0;j<N;j++)
            D[i][j]=INF;
    D[1][0]=0;
    for(int i=1;i<(1<<N);i++)
        for(int j=0;j<N;j++)
			if(i&(1<<j))
				for(int k=0;k<=N;k++)
					if((i&(1<<k))==0)
						D[i+(1<<k)][k]=min(D[i+(1<<k)][k],D[i][j]+Cost[j][k]);
    int Min=INF;
    for(int i=0;i<N;i++)
        Min=min(Min,D[(1<<N)-1][i]+Cost[i][0]);
    if(Min==INF)
        fprintf(OUT,"Nu exista solutie");
    else fprintf(OUT,"%d",Min);
    return 0;
}