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

using namespace std;
FILE *f,*g;

struct bla
{
    int no,co;
};
vector <bla> graph[20];
int ss[1<<19][20];

int main()
{
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    int n,m;
    fscanf(f,"%d %d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&z);
        graph[x].push_back({y,z});
    }
    for(int i=1;i<(1<<n);++i)
        for(int j=0;j<n;++j)
           ss[i][j]=INF;
    ss[1][0]=0;
    int fara,nod;
    for(int i=0;i<(1<<n);++i)
    {
        for(int j=0;j<n;++j)
            if(i & (1<<j))
            {
                fara=i^(1<<j);
                nod=j;
                for(int k=0;k<graph[nod].size();++k)
                {
                    if(i & (1<<graph[nod][k].no))
                        ss[i][j]=min(ss[i][j],ss[fara][graph[nod][k].no]+graph[nod][k].co);
                }
            }
    }
    int so=INF;
    for(int i=0;i<graph[0].size();++i)
        so=min(so,ss[(1<<n)-1][graph[0][i].no]+graph[0][i].co);
    if(so==INF)
        fprintf(g,"Nu exista solutie\n");
    else
        fprintf(g,"%d",so);
    fclose(f);
    fclose(g);
    return 0;
}