#include <fstream>
#define pinf 1000000007
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

int n, m, d[263000][20], nr, c[20][20], ant, p, mini;
int main()
{
    int i, j, k, co;

    fin>>n>>m;

    for (i=0; i<n; i++)
    {
        for (j=0; j<n; j++)
        {
            if (i==j)
            {
                c[i][j]=0;
            }
            else
            {
                c[i][j]=pinf;
            }
        }
    }
    for (k=1; k<=m; k++)
    {
        fin>>i>>j>>co;
        c[i][j]=co;
    }

    nr=((1<<n)-1);

    for (i=3; i<=nr; i=i+2)
    {
        for (j=0; j<n; j++)
            d[i][j]=pinf;
    }

    for (i=3; i<=nr; i=i+2)
    {
        for (j=1; j<n; j++)
        {
            p=1<<j;
            if ( (i&p)>0 )
            {
                ant=i-p;

                if (ant==1)
                {
                    if (c[0][j]!=0)
                    {
                        if (c[0][j]<d[i][j])
                            d[i][j]=c[0][j];
                    }

                }
                else
                {
                    for (k=1; k<n; k++)
                    {
                        if (c[k][j]!=0)
                        {
                            if (d[ant][k]+c[k][j]<d[i][j])
                                d[i][j]=d[ant][k]+c[k][j];
                        }
                    }
                }
            }
        }
    }

    mini=pinf;

    for (i=1; i<n; i++)
    {
        if (c[i][0]!=0 && c[i][0]!=pinf)
        {
            if (d[nr][i]+c[i][0]<mini)
                mini=d[nr][i]+c[i][0];
        }
    }

    if (mini!=pinf)
        fout<<mini;
    else
        fout<<"Nu exista solutie";

    fin.close();
    fout.close();
    return 0;
}