#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
FILE *f,*g;

struct bla
{
    int ve,c;
};

vector <bla> v[20];
int pd[1<<18+1][20];

int main()
{
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    int m,n;
    fscanf(f,"%d %d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[x].push_back({y,c});
    }
    for(int i=0;i<1<<n;++i)
        for(int j=0;j<n;++j)
            pd[i][j]=999999999;
    int config;
    pd[1][0]=0;
    for(int i=0;i<1<<n;++i)
        for(int j=1;j<n;++j)
            if(i & (1<<j))
            {
                config=i^(1<<j);
                for(int k=0;k<v[j].size();++k)
                    if(config & (1<<v[j][k].ve))
                        pd[i][j]=min(pd[i][j],pd[config][v[j][k].ve]+v[j][k].c);
            }
    int mi=999999999;
    for(int i=0;i<v[0].size();++i)
        mi=min(mi,pd[(1<<n)-1][v[0][i].ve]+v[0][i].c);
    if(mi==999999999)
        fprintf(g,"Nu exista solutie");
    else
        fprintf(g,"%d\n",mi);
    fclose(f);
    fclose(g);
    return 0;
}