#include <stdio.h>
#include <vector>
#include <algorithm>

#define Nmax 20
#define INF 1000000000
#define MAX 262150
#define pb push_back

using namespace std;

int n,m,sol,cost[Nmax][Nmax],c[MAX][Nmax];
vector <int> p[Nmax];
vector <int> :: iterator it;

int main()
{
    int i,j;

    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            cost[i][j]=INF;

    for(i=1;i<=m;++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            p[y].pb(x);
            scanf("%d",&cost[x][y]);
        }

    for(i=0; i< 1<<n ; ++i)
        for(j=0; j<n ; ++j)
            c[i][j]=INF;

    c[1][0]=0;

    for(i=0;i<1<<n;++i)
        for(j=0;j<n;++j)
            if(i&(1<<j))
                for(it=p[j].begin();it!=p[j].end();++it)
                    if(i&(1<<*it))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][*it]+cost[*it][j]);

    sol=INF;
    for(it=p[0].begin();it!=p[0].end();++it)
        sol=min(sol,c[(1<<n) - 1][*it] +cost[*it][0]);

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

    return 0;
}