#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

using VI = vector<int>;
using VP = vector<pair<int, int>>;
const int MaxN = 18;
const int Inf = 0x3f3f3f3f;

int N, M;                   // N = nr. de noduri, M = nr. de muchii
vector<VP> G, rG;           // G = graful, rG = graful inversat
int D[1<<MaxN][MaxN];       // D[mask][i] = costul minim daca iau bitii marcati in mask, incep ciclul cu nodul 1 si ultimul nod vizitat este i;
int res;                    // rezultatul (costul minim al unui ciclu hamiltonian)

void Read();                // citesc graful
void Hamilton();            // fac dinamica pt. ciclul hamiltonian de cost minim
void GetResult();           // caut rezultatul res

int main()
{
    Read();
    Hamilton();
    GetResult();

    if ( res < Inf )
        fout << res;
    else
        fout << "Nu exista solutie";

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> N >> M;
    G = rG = vector<VP>(N);

    int x, y, z;
    while (M--)
    {
        fin >> x >> y >> z;

        G[x].push_back({y, z});
        rG[y].push_back({x, z});
    }
}

void Hamilton()
{
    for (int i = 0; i < (1 << N); ++i)
        for (int j = 0; j < N; ++j)
            D[i][j] = Inf;

    D[1][0] = 0;
    for (int mask = 3; mask < (1 << N); mask += 2)
        for (int j = 1; j < N; ++j)
        {
            if ( !(mask & (1 << j)) )
                continue;

            int k, c;
            for (const auto& x : rG[j])
            {
                k = x.first;        // nodul precedent lui j
                c = x.second;       // costul intre acel nod si j

                if ( j == k || !(mask & (1 << k)) )
                    continue;

                D[mask][j] = min(D[mask][j], D[mask ^ (1 << j)][k] + c);
              //  cout << mask << ' ' << j << ' ' << D[mask][j]; cin.get();
            }
        }
}

void GetResult()
{
    res = Inf;

    for (int j = 0; j < N; ++j)
    {
        for (const auto& x : G[j])
            if ( x.first == 0 )
            {
                res = min(res, D[(1 << N) - 1][j] + x.second);
                break;
            }
    }
}