#include <fstream>

using namespace std;

int e,n,i,j,minn=1000000000,d[280000][20],v[3][400];

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>e;
    for (i=1;i<=e;++i)
        fin>>v[0][i]>>v[1][i]>>v[2][i];
    for (i=1;i<=e;++i)
        if (!v[0][i])
            d[1+(1<<v[1][i])][v[1][i]]=v[2][i];
    for (i=1;i<(1<<n)-1;i+=2)
        for (j=1;j<=e;++j)
            if ((v[0][j])&&(d[i][v[0][j]])&&(v[1][j])&&((i/(1<<v[1][j]))%2==0)&&((!d[i+(1<<v[1][j])][v[1][j]])||(d[i+(1<<v[1][j])][v[1][j]]>d[i][v[0][j]]+v[2][j])))
            {
                d[i+(1<<v[1][j])][v[1][j]]=d[i][v[0][j]]+v[2][j];
            }
    for (i=1;i<=e;++i)
        if ((!v[1][i])&&(minn>d[(1<<n)-1][v[0][i]]+v[2][i]))
            minn=d[(1<<n)-1][v[0][i]]+v[2][i];
    if (minn==1000000000) fout<<"Nu exista solutie";
    else fout<<minn;
    return 0;
}