#include <fstream>
#define N 20
#include <vector>
#define INF 2000000000

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int sol[1<<N][N];
struct bla
{
    int ve, co;
};
vector <bla> graph[N];

int main()
{
    int n,m,x,y,c,fara,nod;
    f>>n>>m;
    while(m--)
    {
        f>>x>>y>>c;
        graph[x].push_back({y,c});
    }
    for(int i=0;i<(1<<n);++i)///2^n-1 in reprezentarea binara are toti bitii 1
        for(int j=0;j<n;++j)
            sol[i][j]=INF;
    sol[1][0]=0;
    for(int i=2;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if((i & (1<<j))!=0)
            {
                fara=i ^ (1<<j);
                nod=j;
                for(int k=0;k<graph[nod].size();++k)
                {
                    int vee=graph[nod][k].ve;
                    int cost=graph[nod][k].co;
                    if((i & (1<<vee))!=0)
                        sol[i][j]=min(sol[i][j],sol[fara][vee]+cost);
                }
            }
    int mi=INF;
    nod=0;
    ///fiecare bit de 1 din reprezentarea binara a lui 1<<n-1 marchiaza faptul ca nodul de pe pozitia i exista
    ///dar nodul 0 nu se gaseste
    for(int k=0;k<graph[nod].size();++k)
    {
        int vee=graph[nod][k].ve;
        int cost=graph[nod][k].co;
        mi=min(mi,sol[(1<<n)-1][vee]+cost);
    }
    if(mi!=INF)
        g<<mi<<'\n';
    else
        g<<"Nu exista solutie";
    f.close();
    g.close();
    return 0;
}