#include <cstdio>
#include <cstring>
#define Nmx 20
#define Mmx (1<<18)+10
#define INF 20000001
#define min(a,b) (a<b) ? a : b

using namespace std;

int Cost[Nmx][Nmx],bst[Nmx][Mmx],n,m;
struct nod
{
    int inf;
    nod *urm;
};
nod *G[Nmx];

void add(int x,int y)
{
    nod *aux=new nod;
    aux->inf = y;
    aux->urm = G[x];
    G[x]=aux;
}

void read()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(y,x);
        Cost[x][y]=c;
    }
}

void solve()
{
    memset(bst,INF,sizeof(bst));
    int sol=INF;
    bst[0][1]=0;
    for(int stare=0;stare<(1<<n);++stare)
        for(int i=0;i<n;++i)
        if(stare&(1<<i))
            for(nod *p=G[i];p;p=p->urm)
                if(stare&(1<<p->inf))
                    bst[i][stare]=min(bst[i][stare],bst[p->inf][stare^(1<<i)]+Cost[p->inf][i]);
    for(nod *p=G[0];p;p=p->urm)
        sol=min(sol,bst[p->inf][(1<<n)-1]+Cost[p->inf][0]);
    if(sol==INF)
        printf("Nu exista solutie\n");
    else printf("%d\n",sol);
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    read();
    solve();
    return 0;
}