#include <fstream>
#include <vector>
#define nmax 20
#define inf 18000005
using namespace std;
fstream f1("hamilton.in", ios::in);
fstream f2("hamilton.out", ios::out);
int n, m, ct[nmax][nmax], cost[nmax][524288], rez=inf;
vector <int> v[nmax];
void citire()
{
    int i, j, x, y, c;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            ct[i][j]=inf;
    ////costuri muchii initializate cu infinit
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        ct[x][y]=c; //retii costurile muchiilor
        v[y].push_back(x);
        //retii graful transpus
    }
}
void pd()
{
    int i, j, nod;
    //cost[i][j]=costul minim al unui lant hamiltonian care se termina cu nodul i si are configuratia de noduri prezenta in el j
    //toate ciclurile pornesc din nodul 0
    //setezi matricea de costuri pe inf
    for(i=0; i<n; i++)
        for(j=0; j<(1<<n); j++)
            cost[i][j]=inf;
    //costul lantului format doar din nodul 0 este 0
    //ciclul tau contine initial doar nodul 0 (un singur inceput)
    cost[0][1]=0;

    for(j=1; j<(1<<n); j++) //mergi pe configuratia de noduri
        for(i=0; i<n; i++) //mergi pe nodul de final (tu il alegi, nu e neaparat precizat prin dinamica)
            if(j&(1<<i)) //daca nodul final i face parte din configuratie j
        {
            //iei un vecin nod de al lui i a.i. exista muchie de la nod la i
            for(auto it=v[i].begin(); it!=v[i].end(); ++it)
                if(j&(1<<(*it))) //daca nod face parte din configuratie
            {
                nod=*it;///exista muchie de la v la i
                cost[i][j]=min(cost[i][j], cost[nod][j^(1<<i)]+ ct[nod][i]);
                //faci minimul dintre costul curent  si costul lantului hamilt minim
                //care se termina cu nod si contine config j fara nodul i plus costul muchiei de la nod la i
            }

        }

    for(auto it=v[0].begin(); it!=v[0].end(); ++it) //ciclul hamiltonian incepe cu un nod *it
        rez=min(rez, cost[*it][(1<<n)-1]+ ct[*it][0]);
    //pp ca nodul dat e vecin cu nodul 0 , deci ciclul e lantul care se termina cu *it plus costul muchiei de la it la 0
    ///(ciclul incepe cu nodul 0)
    if(rez==inf) f2<< "Nu exista solutie" <<"\n";  //nu ai gasit un  ciclu hamiltonian
    else f2<<rez<<"\n";
}
int main()
{
    citire();
    pd();
    return 0;
}