#include<cstdio>
#include<vector>
#include<cstring>
#define oo 1<<30
using namespace std;
int N,M,sol=oo;
int C[1<<18][20];
int Cost[20][20];
vector<int> GT[20];
int calc(int x,int y)
{
    if(C[x][y] != -1) return C[x][y];

    int i;
    vector<int>::iterator it;
    C[x][y]=oo;
    for(it=GT[y].begin();it!=GT[y].end();it++)
    {
        i=*it;
        if(x & (1<<i)) //face parte din lant
            C[x][y]=min(C[x][y],calc(x ^ (1<<y),i)+Cost[i][y]);
    }
    return C[x][y];
}
int main()
{
    int a,b,c;
    vector<int>::iterator it;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(;M;--M)
    {
        scanf("%d%d%d",&a,&b,&c);
        Cost[a][b]=c;
        GT[b].push_back(a);
    }
    memset(C,-1,sizeof(C));
    C[1][0]=0;
    for(it=GT[0].begin();it!=GT[0].end();it++)
        sol=min(sol,calc((1<<N)-1,*it)+Cost[*it][0]);
    if(sol==oo) printf("Nu exista solutie\n");
    else printf("%d\n",sol);
    return 0;
}