#include <iostream>
#include <fstream>
#define inf 18100000
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int n,m,a,b,c,ma[20][20];
long long d[262200][20];
int main()
{
    fin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(i==j)
                ma[i][j]=0;
            else
                ma[i][j]=inf;
        }

    for(;m;m--)
    {
        fin>>a>>b>>c;
        ma[a][b]=c;
    }




    for(int i=3;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            d[i][j]=inf;


    for(int i=3;i<(1<<n);i=i+2)
    {
        ///fout<<i<<":"<<endl;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                ///d[i][j]
                ///fout<<j<<"   "<<i-(1<<j)<<endl;
                for(int k=0;k<n;k++)
                {
                    if((i-(1<<j))&(1<<k))
                    {
                       /// if(ma[k][j])
                        {
                            ///fout<<i-(1<<j)<<" "<<k<<" "<<k<<" "<<j<<endl;
                            d[i][j]=min(d[i][j],d[i-(1<<j)][k]+ma[k][j]);
                        }
                    }
                }
                ///fout<<"      "<<d[i][j]<<endl;

            }

        }
        ///fout<<endl;
    }
    ///fout<<endl<<endl;
    long long minn=inf;
    for(int i=0;i<n;i++)
    {

        if(d[(1<<n)-1][i]!=inf&&ma[i][0])
        {
            minn=min(minn,d[(1<<n)-1][i]+ma[i][0]);
        }
        ///fout<<d[(1<<n)-1][i]<<" "<<i<<endl;

    }
    if(minn==inf)
        fout<<"Nu exista solutie";
    else
        fout<<minn;
    return 0;
}