// graf orientat cu N vârfuri şi M muchii, fiecare arc având asociat un cost
// ciclu hamiltonian = conţine fiecare nod din graf exact o singură dată
#include <iostream>
#include <fstream>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;

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

vector<int> g[20];
int n, m, cost[22][22], sol;
int dp[262150][22]; // matricea costurilor tuturor drumurilor

void hamilton()
{
    int maxim = 1<<n;
    // se init matricea costurilor tuturor drumurilor cu infinit
    for(int i = 0; i < maxim; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = inf;

    dp[1][0] = 0; // nodul de inceput 0, care are costul 0

    // Pentru fiecare lant, se verifica nodurile care fac parte din acesta si se actualizeaza costul minim <=>
    // pentru fiecare drum, parcurgem toate nodurile grafului si, pentru nodurile care fac parte din drum, incercam sa actualizam costurile minime ale drumurilor pana la j prin i
    for(int i = 0; i < maxim; i++)
        for(int j = 0; j < n; j++) {
            if (i && (1<<i))     // i este drumul; j este nodu; daca j face parte din i, atunci bitul de pe pozitia j din i este 1
            {
                // daca nodul j face parte din drumul curent i, parcurgem vecinii nodului j si, daca vecinul face parte si el din drum, atunci incercam sa actualizam costul minim al drumului
                // pana la nodul j prin drumul i
                for (int k=0; k<n; k++)
                {
                    // daca vecinul nodului apartine drumului, verificam daca e cazul sa actualizam minimul costurilor drumurilor pana la nodul j prin drumul i
                    // cu suma dintre costul minim pana la vecin + costul muchiei de la vecin la j
                    if (cost[k][j] && i & (1 << k)) {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + cost[k][j]); }
                }
            }
        }

    // caut costul minim al nodurilor care ajung in nodul 0, deoarece cu acesta am inceput
    sol = inf;
    for (int i=0; i<n; i++)
        if (cost[i][0])
            sol = min(sol, dp[maxim-1][i] + cost[i][0]);

    if(sol == inf)  // daca a ramas infinit, inseamna ca graful nu este hamiltonian
        fout << "Nu exista solutie";
    else
        fout << sol << "\n";
}

int main()
{
    int x, y, c;
    fin >> n >> m;

    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> c; // arc intre x si y, cu costul c
        g[x].push_back(y); // orientat
        cost[x][y] = c;
    }

    hamilton();

    return 0;
}