#include <iostream>
#include <fstream>
#include <vector>

#define Infinit 100000005

using namespace std;

vector <int> G[20];
int N, S=Infinit, Best[1000000][20], Cost[20][20];

void Read ()
{
    ifstream fin ("hamilton.in");
    int M, X, Y;
    fin >> N >> M;
    for (int i=0; i<N; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            Cost[i][j]=Infinit;
        }
    }
    for (; M>0; --M)
    {
        fin >> X >> Y;
        fin >> Cost[X][Y];
        G[Y].push_back (X);
    }
    fin.close ();
}

inline void Type ()
{
    ofstream fout ("hamilton.out");
    if (S==Infinit)
    {
        fout << "Nu exista solutie";
    }
    else
    {
        fout << S << "\n";
    }
    fout.close ();
}

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

int main()
{
    int n, Stare[20];
    Read ();
    n=1<<N;
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            Best[i][j]=Infinit;
        }
    }
    Best[1][0]=0;
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            if (i&(1<<j)!=0)
            {
                for (unsigned k=0; k<G[j].size (); ++k)
                {
                    if (i&(1<<G[j][k])!=0)
                    {
                        Best[i][j]=Min (Best[i][j], Best[i^(1<<j)][G[j][k]]+Cost[G[j][k]][j]);
                    }
                }
            }
        }
    }
    for (unsigned i=0; i<G[0].size (); ++i)
    {
        S=Min (S, Best[n-1][G[0][i]]+Cost[G[0][i]][0]);
    }
    Type ();
    return 0;
}