#include <fstream>
#include <vector>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int inf = 1 << 25;
int n , m , cost[20][20] , dp[262150][20] , x , y , sol;
vector<int> G[20];

int main()
{
    f >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) cost[i][j] = inf;//initializare

    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y;
        G[y].push_back(x);//graful transpus !!!
        f >> cost[x][y];//nu transpun si costurile!!
    }

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

    dp[1][0] = 0;//drumul de nodul 0 care se termina in nodul 0 are LUNGIME 0

    for(int i = 0; i < (1 << n); ++i)// iau toate multimile
        for(int j = 0; j < n; ++j)// iau toate finalurie pt multime
            if(i & (1 << j))// daca j se afla in multime
                for(auto it = G[j].begin(); it != G[j].end(); ++it)//iau vecinii lui j
                    if(i & (1 << *it))//daca vecinul lui j se afla in multime
                        dp[i][j] = min(dp[i][j] , dp[i ^ (1 << j)][*it] + cost[*it][j]);//il scot pe j din multime
                                                                                        //calculez drumu de la it la j si daca e mai mic relaxe. gen dijkstra
    sol = inf;
    for(auto it = G[0].begin(); it != G[0].end(); ++it)
        sol = min(sol , dp[(1 << n) - 1][*it] + cost[*it][0]);//sol se afla in multime 1111...111(de n - 1) si mai adaug costul muchiei care inchide ciclul

    if(sol == inf) g << "Nu exista solutie" << "\n";
    else           g << sol << "\n";

    return 0;
}