#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf = 100000000;
int n,m,sol,i,j,x,y;
int cost[25][25];
int aux[263000][25];
vector <int> q[25];
int main()
{
	fin >> n >> m;
	for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            cost[i][j] = 1999999999;
        }
    }
	for (i=1;i<=m;i++)
	{
		fin>>x>>y;
		q[y].push_back(x);
		fin>>cost[x][y];
	}
	for (i=0;i<=(1<<n)-1;i++)
    {
        for (j=0;j<=n-1;j++)
        {
            aux[i][j]=1999999999;
        }
    }
    aux[1][0]=0;
	for (i=0;i<=(1<<n)-1;i++)
    {
        for (j=0;j<n;j++)
        {
            if (i & (1<<j))
            for (size_t k=0;k<q[j].size();k++)
            {
                if (i & (1<<q[j][k]))
                aux[i][j]=min(aux[i][j],aux[i^(1<<j)][q[j][k]]+cost[q[j][k]][j]);
            }
        }
    }
	sol=inf;
	for (size_t i=0;i<q[0].size();i++)
    {
        sol=min(sol,aux[(1<<n)-1][q[0][i]]+cost[q[0][i]][0]);
    }
	if(sol==inf) fout<<"Nu exista solutie"<<'\n'; ///nu avem solutii
	else fout<<sol; ///afisam solutia
	return 0;
}