#include <fstream>

using namespace std;
int v[20][20],d[1<<19][20],re[1<<19],n,m,x,y,c,i,j,t,r,q,b1,b2,sol;
int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        v[x][y]=c;
    }
    for(i=1,j=0; i<1<<18; i*=2,j++)
        re[i]=j;
    for(i=0; i<(1<<n); i++)
    for(j=0; j<n; j++)
        d[i][j]=1000000000;
    d[1][0]=0;
    for(i=1; i<(1<<n); i++)
    {
        r=i;
        q=(((1<<n)-1)^r);
        for(j=r; j>=1; j-=(j&(-j)))
        {
            b1=(j&(-j));
            for(t=q; t>=1; t-=(t&(-t)))
            {
                b2=(t&(-t));
                if(v[re[b1]][re[b2]])
                    d[i+b2][re[b2]]=min(d[i+b2][re[b2]],d[i][re[b1]]+v[re[b1]][re[b2]]);
            }
        }
    }
    sol=1000000000;
    for(i=1; i<n; i++)
        if(v[i][0])
            sol=min(sol,d[(1<<n)-1][i]+v[i][0]);
    if(sol!=1000000000)
        g<<sol<<'\n';
    else
        g<<"Nu exista solutie\n";
    f.close(); g.close();
    return 0;
}