#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int maxn = 20;
const int maxx = 262150;
const int inf = 100000000;
int n,m,sol,i,j,x,y;
int dp[maxn][maxn];
int aux[maxx][maxn];
vector <int> q[maxn];
int main()
{
	fin >> n >> m;
	for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            dp[i][j] = inf;
        }
    }
	for (i=1;i<=m;i++)
	{
		fin>>x>>y;
		q[y].push_back(x);
		fin>>dp[x][y];
	}
	for (i=0;i < 1 << n;i++)
    {
        for (j=0;j<n;j++) aux[i][j]=inf;
        {
            aux[1][0]=0;
        }
    }
	for (i=0;i < 1 << n;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]]+dp[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]]+dp[q[0][i]][0]);
    }
	if(sol==inf) fout<<"Nu exista solutie"<<'\n'; ///nu avem solutii
	else fout<<sol; ///afisam solutia
	return 0;
}