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

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

const int NMAX = 19,
          XMAX = (1 << 18), ///262144
          INF = 1 << 30;

int N, M, NN,
    Cost[NMAX][NMAX],
    C[XMAX][NMAX];
vector <int> G[NMAX];

void citire()
{
    int x, y, i, j;
    f >> N >> M;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            Cost[i][j] = INF;
    //
    for(i = 1; i <= M; i++)
    {
        f >> x >> y;
        G[y].push_back(x);///*
        f >> Cost[x][y];
    }
    NN = (1 << N) - 1;
}

int calcul(int cfg, int j)///Folosim memoizare
{
    if(C[cfg][j] == -1)
    {
        C[cfg][j] = INF;
        //
        ///Se parcurg nodurile care arata spre ultimul nod din lant
        for(int &x : G[j])
        {
            if(cfg & (1 << x))///Se aleg doar cele care apartin lantului
            {
                if(x == 0 && cfg != (1 << j) + 1)
                    continue;///Primul nod trebuie scos ultimul
                C[cfg][j] = min(C[cfg][j], calcul(cfg ^ (1 << j), x) + Cost[x][j]);
            }
        }
    }
    return C[cfg][j];
}

int main()
{
    int Sol = INF;
    citire();
    //
    for(int i = 0; i <= NN; i++)
        for(int j = 0; j < N; j++)
            C[i][j] = -1;
    C[1][0] = 0;
    for(int &nod : G[0])///Se parcurg nodurile din care se ajunge in 0
        Sol = min(Sol, calcul(NN, nod) + Cost[nod][0]);
    if(Sol == INF)
        g << "Nu exista solutie";
    else
        g << Sol;
    f.close();
    g.close();
    return 0;
}