#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
const char iname[]="hamilton.in";
const char oname[]="hamilton.out";
const int maxn=18;
const int INF=0x3f3f3f3f;
ifstream f(iname);
ofstream g(oname);
int cost[maxn][maxn],i,j,n,m,a[1<<maxn][maxn],x,y,z,mint;
vector<int> E[maxn];
int sol(int bytes,int nod)
{
    if(a[bytes][nod]==-1)
    {
        a[bytes][nod]=INF;
        for(vector<int>::iterator it=E[nod].begin();it!=E[nod].end();++it)
            if((1<<*it)&bytes)
            {
                if(*it==0&&bytes!=(1<<nod)+1)
                    continue;
                a[bytes][nod]=min(a[bytes][nod],sol(bytes-(1<<nod),*it)+cost[*it][nod]);
            }
    }
    return a[bytes][nod];
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        E[y].push_back(x);
        cost[x][y]=z;
    }

    memset(a,-1,sizeof(a));
    a[1][0]=0;
    mint=INF;
    for(vector<int>::iterator i
    if(mint==INF)t=E[0].begin();it!=E[0].end();++it)
        mint=min(mint,sol((1<<n)-1,*it)+cost[*it][0]);

    if(mint==INF)
        g<<"Nu exista solutie\n";
    else
        g<<mint<<"\n";

    f.close();
    g.close();
    return 0;
}