#include<stdio.h>
#include<limits.h>
#include<vector>
#include<algorithm>
#define MAXV 18
#define INF 1000000000
FILE*fin,*fout;

int Cost[MAXV+1][MAXV+1];
int d[(1<<MAXV)+1][MAXV+1];
std::vector<int> fathers[MAXV+1];

int main()
{
    fin=fopen("hamilton.in","r");
    fout=fopen("hamilton.out","w");
    int V,E;
    fscanf(fin,"%d%d",&V,&E);
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j) Cost[i][j] = INF;
    for(int i=1; i<=E; i++)
    {
        int x,y,cost;
        fscanf(fin,"%d%d%d",&x,&y,&cost);
        Cost[x][y]=cost;
        fathers[y].push_back(x);
    }
    for(int j=0;j<(1<<V);j++)
    {
        for(int k=0;k<V;k++)
        {
            d[j][k]=INF;
        }
    }
    d[1][0]=0;
    for(int j=0; j<(1<<V); j++)
    {
        for(int k=0; k<V; k++)
        {
            if(j & (1<<k))
            {
                for(int i=0; i<fathers[k].size(); i++)
                {
                    int v=fathers[k][i];
                    if(j & (1<<v))
                    {
                        d[j][k]=std::min(d[j][k],d[j ^(1<<k)][v] + Cost[v][k]);
                    }
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<fathers[0].size();i++)
    {
        int vec=fathers[0][i];
        ans=std::min(ans,d[(1<<V)-1][vec]+Cost[vec][0]);
    }
    if(ans!=INF)
    {
        fprintf(fout,"%d",ans);
    }
    else
    {
        fprintf(fout,"Nu exista solutie");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}