#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define maxn 25
#define maxmask 1<<18
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
int s[maxmask][maxn],c[maxn][maxn];
vector <int> lt[maxn];

void read()
{
    int i,j;
    int x,y,cost;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
     for(j=0;j<n;j++)
      if(i!=j)
       c[i][j]=inf;

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

void det(int mask,int k)
{
    int minn=inf,newk;
    int newmask=mask^(1<<(k-1));
    for(unsigned int i=0;i<lt[k].size();i++)
    if(lt[k][i])
    {
        newk=lt[k][i];
        if( ((mask>>(newk-1))&1) )
        {
            if( !s[newmask][newk] ) det(newmask,newk);
            minn=min(minn,s[newmask][newk]+c[newk][k]);
        }
    }
    s[mask][k]=minn;
}

void solve()
{
    int sol=inf,maskf=(1<<(n-1))-1;

    for(int i=1;i<n;i++) s[1<<(i-1)][i]=c[0][i];
    for(unsigned int i=0;i<lt[0].size();i++)
    {
        det(maskf,lt[0][i]);
        sol=min(sol,s[maskf][lt[0][i]]+c[lt[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();

    fclose(stdin);
    fclose(stdout);
    return 0;
}