#include <iostream>
#include <fstream>
using namespace std;
ifstream ka("hamilton.in");
ofstream ki("hamilton.out");

const int N_MAX = 18;
const int M_MAX = 18 * 17;
const int MAX_MUCHIE = 1000000;

int n, m;
int x, y, c;
int muchie[N_MAX + 1][N_MAX + 1];
int stare[1 << N_MAX][N_MAX + 1];
long long minim = MAX_MUCHIE * M_MAX + 1;

long long hamilton(int numar_nr, int configuratie, int terminatie)
{
    if(!stare[configuratie][terminatie])
    {
        if(numar_nr == 1)
        {
            if(muchie[x][terminatie])
                stare[configuratie][terminatie] = muchie[x][terminatie];
            else
                stare[configuratie][terminatie] = MAX_MUCHIE * M_MAX + 1;
        }
        else
        {
            long long minn = MAX_MUCHIE * M_MAX + 1;
            for(int i = 0; i < n; i++)
            {
                if(i != x)
                {
                    if(muchie[i][terminatie] && configuratie & (1 << i))
                    {
                        long long raspuns = hamilton(numar_nr - 1, configuratie - (1 << terminatie), i) + muchie[i][terminatie];
                        if(raspuns < minn)
                            minn = raspuns;
                    }
                }
            }
            stare[configuratie][terminatie] = minn;
        }
    }
    return stare[configuratie][terminatie];
}

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        ka >> x >> y >> c;
        if(c < muchie[x][y] || muchie[x][y] == 0)
        {
            muchie[x][y] = c;
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(muchie[i][x])
        {
            int rezultat = hamilton(n - 1, (1 << n) - 1, i) + muchie[i][x];
            if(rezultat < minim)
                minim = rezultat;
        }
    }
    if(minim < MAX_MUCHIE * M_MAX + 1)
        ki << minim;
    else
        ki << "Nu exista solutie";
}