#include <iostream>
#include <vector>
#include <fstream>
#define inf 1e9
#define NMAX 19

using namespace std;

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

int cost[NMAX][NMAX];
vector<int> g[NMAX];
int dp[1<<NMAX][NMAX];
int n,m,x,y,c;

int main()
{
    fin>>n;
    fin>>m;

    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >>c;
        g[y].push_back(x);
        cost[x][y]=c;
    }

    for(int i=0; i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=inf;
        }
    }

    dp[1][0]=0;

    for(int conf =1 ; conf<(1<<n) ; conf++)
    {
        for(int i=0 ; i<n ; i++)
        {
            if(conf&(1<<i))
            {
                int oldconf = conf ^ (1<<i);
                for(int j : g[i])
                {
                    if(oldconf & (1<<j))
                    {
                        dp[conf][i] = min(dp[conf][i],dp[oldconf][j] + cost[j][i]);
                    }
                }
            }
        }
    }

    int sol = inf;
    for(auto i : g[0])
        sol = min(sol,dp[(1<<n)-1][i] + cost[i][0]);
    if(sol==inf)
        fout << "Nu exista solutie" << '\n';
    else
        fout << sol << '\n';
    return 0;
}