#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int inf=100000000;
vector<int>v[20];
vector<int>::iterator it;
int cost[20][20],din[263000][20],n,m,i,j,x,y,sol;

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++) din[i][j]=inf;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++) cost[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        scanf("%d",&cost[x][y]);
        v[y].push_back(x);
    }
    din[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if(i&(1<<j))
                for(it=v[j].begin();it!=v[j].end();it++)
                    if(i&(1<<*it))
                        din[i][j]=min(din[i][j], din[i^(1<<j)][*it]+cost[*it][j]);
    sol=inf;
    for(it=v[0].begin();it!=v[0].end();it++)
        sol=min(sol, din[(1<<n)-1][*it]+cost[*it][0]);
    if(sol==inf) printf("Nu exista solutie");
    else printf("%d",sol);
    return 0;
}