#include<stdio.h>
#include<assert.h>
#include<vector>
#include<algorithm>
using namespace std;

#define OVER9000 100000000

vector<int>a[22];
int n,m,lim,sol=OVER9000,cost[20][20],d[300000][22];

void read()
{
    assert(freopen("hamilton.in","r",stdin)!=NULL);
    int i,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cost[i][j]=OVER9000;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x].push_back(y);
        cost[x][y]=c;
    }
}

void hamilton()
{
    int i,j,k,p;
    for(i=0;i<lim;++i)
        for(j=0;j<n;++j)
            for(k=0,p=1;k<n;++k,p<<=1)
                if(cost[j][k]!=OVER9000 && !(i&p))
                    d[i+p][k]=min(d[i+p][k],d[i][j]+cost[j][k]);
}

void solve()
{
    int i,j;
    lim=1<<n;
    for(i=0;i<lim;++i)
        for(j=0;j<n;++j)
            d[i][j]=OVER9000;
    d[1][0]=0;
    hamilton();
    for(i=0;i<a[0].size();++i)
        sol=min(sol,d[lim-1][a[0][i]]+cost[a[0][i]][0]);
}

void write()
{
    assert(freopen("hamilton.out","w",stdout)!=NULL);
    if(sol==OVER9000)
        printf("Nu exista solutie");
    else
        printf("%d",sol);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}