#include <iostream>
#include <bits/stdc++.h>
#define inf 1e9
using namespace std;
FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");
int n,a[20][20],c[263000][20],i,j,p,Min,m,x,y,C;
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(i=0; i<=n; i++)
        for(j=0; j<=n; j++)
            a[i][j]=inf;
    for(i=1; i<=m; i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&C);
        a[x][y]=C;
    }
    for(i=0; i<1<<n; i++)
        for(j=0; j<n; j++)
            c[i][j]=inf;
    c[1][0]=0;
    m=(1<<n)-1;
    for(i=0; i<=m; i++)
        for(j=0; j<n; j++)
        {
            if(i&(1<<j))
                for(p=0; p<n; p++)
                    if(a[p][j]!=inf)
                        if(c[i^(1<<j)][p]+a[p][j]<c[i][j])
                            c[i][j]=c[i^(1<<j)][p]+a[p][j];
        }
    Min=inf;
    for(i=1; i<n; i++)
        if(a[i][0]!=inf&&Min>c[m][i]+a[i][0])
            Min=c[m][i]+a[i][0];
    if(Min!=inf)
        fprintf(g,"%d",Min);
    else
        fprintf(g,"Nu exista solutie");
    return 0;
}