#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

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

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

void citire()
{
    int x, y;
    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++)
    {
        fin >> x >> y;
        G[y].push_back(x);
        fin >> Cost[x][y];
    }
    NN = (1 << N)-1;
}

void calcul()
{
    for (int i = 0; i <= NN; i++)
        for (int j = 0; j < N; j++)
            C[i][j] = INF;
    C[1][0] = 0;
    for (int i = 0; i <= NN; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j))
                for (int &x : G[j])
                {
                    if (i & (1 << x))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][x]+Cost[x][j]);
                }
        }
    }
}
int calcul(int cfg, int j)
{
    if (C[cfg][j] == -1)
    {
        C[cfg][j] = INF;
        for (int &x : G[j])
        {
            if (cfg & (1<< x))
            {
                if (x == 0 && cfg != (1<<j)+1)
                    continue;
                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])
    {
        Sol = min(Sol, calcul(NN, nod)+Cost[nod][0]);
    }
    if (Sol == INF)
        fout << "Nu exista solutie";
    else
        fout << Sol;
    return 0;
}