#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=1;j<N;j++)
            for(int k=0;k<N;k++)
                if(i&(1<<k))
                    D[i][j]=min(D[i][j],D[i-(1<<j)][k]+Cost[k][j]);
    int Min=INF;
    for(int i=1;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;
}