#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,sol,i,j,x,y,k,mult;
int cost[25][25];
int dp[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++)
        {
            dp[i][j]=1999999999;
        }
    }
    dp[1][0]=0; ///ciclul pleaca din 0
	for (mult=1;mult<=(1<<n)-1;mult++)
    {
        for (j=0;j<n;j++) ///facem cand se termina in j
        {
            if (mult & (1<<j))
            for (k=0;k<q[j].size();k++) ///scoatem cate un element din multime
            {
                if (mult & (1<<q[j][k]))
                dp[mult][j]=min(dp[mult][j],dp[mult^(1<<j)][q[j][k]]+cost[q[j][k]][j]);
            }
        }
    }
	sol=1999999999;
	for (i=0;i<q[0].size();i++)
    {
        sol=min(sol,dp[(1<<n)-1][q[0][i]]+cost[q[0][i]][0]);
    }
	if(sol==1999999999) fout<<"Nu exista solutie"<<'\n'; ///nu avem solutii
	else fout<<sol; ///afisam solutia
	return 0;
}