#include<algorithm>
using namespace std;
#include<vector>

#define pb push_back
#define DIM (1<<18)+5
#define INF 1<<30

vector <int> lst[20];
int n,m,c[20][20],h[DIM][20];

void read ()
{
    int i,nr1,nr2,nr3,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            c[i][j]=INF;
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&nr1,&nr2,&nr3);
        lst[nr1].pb (nr2);
        c[nr1][nr2]=nr3;
    }
}

void solve ()
{
    int i,j;
    for(i=0;i<(1<<n);++i)
        for(j=0;j<n;++j)
            h[i][j]=INF;
    h[1][0]=0;
    for(i=0;i<(1<<n);++i)
        for(j=0;j<n;++j)
            if(i&(1<<j))
                for(size_t k=0;k<lst[j].size ();++k)
                    if(i&(1<<lst[j][k]))
                        h[i][j]=min(h[i][j],h[i^(1<<j)][lst[j][k]]+c[lst[j][k]][j]);
    int sol=INF;
    for(size_t i=0;i<lst[0].size ();++i)
            sol=min(sol,h[(1<<n)-1][lst[0][i]]+c[lst[0][i]][0]);

    if(sol==INF)
        printf("Nu exista solutie");
    else
        printf("%d",sol);
}

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