#include <iostream>
#include <fstream>
#include <algorithm>
#define inf 999999999
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,c[20][20],np,mc=2*inf;
int L[1048576][20];
int main()
{
    f>>n>>m;
    np=1<<n;
    for(int i=0;i<=np;++i)for(int j=0;j<=n;++j)L[i][j]=inf;
    for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)c[i][j]=inf;
    for(int i=1;i<=m;++i){int x,y,t;f>>x>>y>>t;c[x][y]=t;}
    L[1][0]=0;
    for(int i=1;i<np;++i)for(int j=1;j<n;++j)if((i&(1<<j))>0)for(int k=0;k<=n;++k)if(c[k][j]<inf&&(i&(1<<k))>0)
        {L[i][j]=min(L[i][j],L[i^(1<<j)][k]+c[k][j]);}//cout<<(i^(1<<j))<<"->"<<i<<' '<<k<<"->"<<j<<'+'<<c[k][j]<<' '<<L[i][j]<<'\n';}
    for(int i=1;i<=n;++i)if(c[i][0]<inf)mc=min(mc,L[np-1][i]+c[i][0]);
    if(mc<inf)g<<mc;
    else g<<"Nu exista solutie";
}