#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const short Nmax = 19;
const int inf = 1000000000;
int cost[Nmax][Nmax] , n , m , dp[Nmax][1 << Nmax] , valmax;
vector < int > L[Nmax];
queue < pair < int , int > > Q;
int main()
{
    int x , y , c , stare , newstare , nod;
    fin >> n >> m;
    valmax = (1 << n) - 1;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0; j < n ; j++)
            cost[i][j] = inf;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j <= valmax ; j++)
            dp[i][j] = inf;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        L[x] . push_back(y);
        cost[x][y] = c;
    }
    nod = 0;
    stare = 1;
    dp[nod][stare] = 0;
    Q . push({nod , stare});
    while(! Q . empty())
    {
        nod = Q . front() . first;
        stare = Q . front() . second;
        Q . pop();
        for(auto w : L[nod])
        {
            if(( stare & (1 << w) ) == 0)
            {
                if(dp[w][stare | (1 << w)] > dp[nod][stare] + cost[nod][w])
                {
                    newstare = ( stare | (1 << w) );
                    dp[w][stare | (1 << w)] = dp[nod][stare] + cost[nod][w];
                    Q . push({w , newstare});
                }
            }
        }
    }
    int sol = inf;
    for(int i = 0 ; i < n ; i++)
        sol = min(sol , dp[i][valmax] + cost[i][0]);
    if(sol == inf)
        fout << "Nu exista solutie\n";
    else fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}