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

using namespace std;
FILE *f,*g;

struct name
{
    int ve,c;
};
vector <name> v[20];
int pd[1<<18][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);
        v[x].push_back({y,z});
    }
    for(int i=0;i<1<<n;++i)
        for(int j=0;j<n;++j)///nodurile sunt indexate de la 0
            pd[i][j]=1999999999;
    for(int i=0;i<n;++i)///distanta de la nodul i la configuratia in care se gaseste doar el e 0, pe baza ipotezei
        pd[1<<i][i]=0;
    int config;
    for(int i=1;i<1<<n;++i)
        for(int j=0;j<n;++j)
            if(i & (1<<j))
            {
                config=i ^ (1<<j);///elimin nodul j din configuratia lui i
                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);
            }
    /*for(int i=0;i<1<<n;++i)
    {
        for(int j=0;j<n;++j)
            fprintf(g,"%d ",pd[i][j]);
        fprintf(g,"\n");
    }*/
    int sol=1999999999;
    for(int i=0;i<v[0].size();++i)
    {
        int cost=v[0][i].c;
        sol=min(sol,pd[(1<<n) - 1][v[0][i].ve]+v[0][i].c);
    }
    if(sol==1999999999)
        fprintf(g,"Nu exista solutie\n");
    else
        fprintf(g,"%d",sol);
    fclose(f);
    fclose(g);
    return 0;
}