#include <iostream>
#include <fstream>
#define NMax 18
#define MMax 210
#define inf 20000005
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m,dp[(1<<NMax)+1][NMax],cost[NMax][NMax],sol=inf;


int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int c,x,y;
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<=n-1; j++)
            dp[i][j]=inf;
    dp[1][0]=0;
    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<=n-1; j++)
        {
            if(((i>>j)&1)==1)
            {
                for(int v=0; v<n; v++)
                {
                    if(((i>>v) & 1)==1 && cost[v][j]!=0 && v!=j)
                    {
                            dp[i][j]=min(dp[i^(1<<j)][v]+cost[v][j],dp[i][j]);
                    }

                }
                if(i==(1<<n)-1)
                {
                    if(cost[j][0]!=0)
                    sol=min(sol,dp[i][j]+cost[j][0]);
                }
            }

        }
    }
    if(sol==inf)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
}