#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 20;
const int MAXX = (1<<18) + 6;
const int INF = 100000000;

int N, M, Sol;
vector <int> A[MAXN]; // muchiile inverse
int Cost[MAXN][MAXN]; // costul unei muchii
int C[MAXX][MAXN]; //costul pentru un lant ce contine nodurile "MAXX" si se termina cu nodul "MAXN"

int calc(int start, int conf, int last)
{
    if (C[conf][last] == -1)
    //intr-un final se va ajunge la primul nod din lant, adica conf contine doar pe "last"
    //care e si first actual, si costul de la un nod la el insusi este 0.Se returneaza 0.
    {
        C[conf][last] = INF;

        for (size_t i = 0; i < A[last].size(); ++i)
        //pentru toate nodurile anterioare ultimului
            if (conf & (1<<A[last][i]))
            //daca exista nodul anterior respectiv (am retinut muchia inversa)
            {
                if (A[last][i] == start && ((conf ^ (1<<last)) != (1<<start))) continue;
                //daca nodul nodul anterior este primul si mai exista si alte noduri
                //inafara de primul si ultimul, sare peste pas.

                C[conf][last] = min(C[conf][last], calc(start, conf ^ (1<<last), A[last][i]) + Cost[A[last][i]][last]);
                //lantul ce contine nodurile (conf) si se termina cu last
                //reprezinta minimul dintre solutiile ce nu il contin pe last (in conf)
                //si ultimul nod devine cel anterior lui last + costul muchiei de la nodul anterior la last.

            }
    }

    return C[conf][last]; //returneaza lantul ce contine nodurile conf si se termina cu last
    // si are valoare minima. A fost verificat: Pentru toate nodurile anterioare,
    // se alege costul minim dintre (C[conf_fara_last][ant_lui_last]
    // + costul de la ant_lui_last la last).
}

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

    fin >> N >> M;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) Cost[i][j] = INF;

    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;

        fin >> x >> y >> c;

        A[y].push_back(x); // retin muchia invers
        Cost[x][y] = c;
    }

    Sol = INF;

    for (int i = 0; i < N; ++i)
    {
        int nod = i;
        memset(C, -1, sizeof(C));

        C[1<<i][i] = 0;//lantul ce contine doar nodul i si se termina cu i are lungime 0.

        for (size_t j = 0; j < A[i].size(); ++j)
        {
            int nodant = A[i][j];
            Sol = min(Sol, calc(nod, (1<<N)-1, nodant) + Cost[nodant][nod]);
            //Sol devine minimul dintre toate solutiile ce incep cu nodul nod si se termina
            //cu nodul anterior lui, care va fi ultimul din ciclu. (Exista muchie(nodant,nod)).
        }
    }

    if (Sol != INF) fout << Sol << endl;
    else fout << "Nu exista solutie" << endl;

    return 0;
}