#include <iostream>
#include <fstream>
#define inf 1000000000

using namespace std;

int n, m, sol;
int cost[20][20];
int solutii[20][1<<20];
 
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
 
void citeste ()
{
    fin>>n>>m;
	
    int a, b, c;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        cost[++a][++b]=c;
    }
}
 
 
int bkt (int ant, int x)
{
    if (solutii[ant][x]!=0)
        return solutii[ant][x];
    else
    {
        if (x==(1<<n+1)-2)
        {
            if(cost[ant][1] != 0)
                solutii[ant][x] = cost[ant][1];
            else
                solutii[ant][x] = inf;
        }
        else
        {
            int minim, sol;
            minim=inf;
            for (int i=2; i<=n; i++)
            {
                if (cost[ant][i]!= 0 && (x & (1<<i)) == 0)
                {
                    sol=cost[ant][i]+bkt (i, x ^ (1<<i));
                    if (minim>sol) 
						minim=sol;
                }
            }
            solutii[ant][x]=minim;
        }
        return solutii[ant][x];
    }
}
 
int main ()
{
    citeste ();
	
    sol=bkt (1, 1 << 1);
	
    if (sol==inf) 
		fout<<"Nu exista solutie";
    else 
		fout<<sol;
    return 0;
}