#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
#define MAXN 21
#define INF 0x3f3f3f3f


int cost[21][21], dp[1<<20][21];
int i,j,n,m,x,y,k,urm,sol;
vector<int> graf[21];

int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        graf[y].push_back(x);
        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)) // configuratia actuala il contine pe j
            {
                for(k=0; k<graf[j].size(); k++)
                {
                    urm=graf[j][k]; //urmatorul nod care iese din j
                     if(i&( 1<<urm )) // daca conf il contine pe nodul urmator
                        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;
}