#include <fstream>
#include <vector>
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
#define MAXN 1<<20
#define INF 9999999

vector<int> graf[21];
int cost[21][21],dp[MAXN][21];

int i,j,k,x,y,n,m,urm,sol;
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        graf[y].push_back(x); // x intra in y
        cin>>cost[x][y];
    }

    for(i=0; i< 1<<n; i++)
        for(j=0; j<n; j++)
            dp[i][j]=INF;

    dp[1][0]=0;
    for(i=1; i< 1<<n; i++)
        for(j=0; j<n; j++)
            if(i&( 1<<j )) // conf actuala il contine pe j
            {
                for(k=0; k<graf[j].size(); k++)
                {
                    urm=graf[j][k]; // urmatorul nod care intra in j
                    if(i&( 1<<urm ))
                        dp[i][j]=min(dp[i][j],dp[i^( 1<< j)][urm] + cost[urm][j]);
                }
            }
    sol=INF;
    for(i=0; i<graf[0].size(); i++)
        sol=min(sol,dp[ ( 1<<n )-1 ][graf[0][i]] + cost[graf[0][i]][0]);

    if(sol==INF)
        cout<<"Nu exista solutie";
    else
        cout<<sol;



}