#include <cstdio>
#include <vector>
#include <iostream>
#define INF 2000000000

using namespace std;
FILE *f,*g;

struct bla
{
    int vecin,cost;
};
vector < bla > graph[20];
int sol[1<<19][20];

int main()
{
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    int n,m,x,y,z;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&z);
        graph[y].push_back({x,z});
    }
    for(int i=0;i<1<<n;++i)
        for(int j=0;j<n;++j)
            sol[i][j]=INF;
    sol[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<graph[j].size();++k)
                    if(i & (1<<graph[j][k].vecin))
                        sol[i][j]=min(sol[i][j],sol[i ^ (1<<j)][graph[j][k].vecin]+graph[j][k].cost);
    /*for(int i=0;i<1<<n;++i)
    {
        for(int j=0;j<n;++j)
            fprintf(g,"%d ",sol[i][j]);
        fprintf(g,"\n");
    }*/
    int so=INF;
    for(int i=0;i<graph[0].size();++i)
        so=min(so,sol[(1<<n) -1][graph[0][i].vecin]+graph[0][i].cost);
    if(so==INF)
        fprintf(g,"Nu exista solutie");
    else
        fprintf(g,"%d\n",so);

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