#include <fstream>
#include <vector>
#include <cstring>

#define In "hamilton.in"
#define Out "hamilton.out"
#define Inf 0x3f3f3f3f
#define Nmax 18
#define max_stare (1<<18)
#define min(a,b) ((a)<=(b)?(a):(b))

using namespace std;

int N,Mstare;
int best[Nmax][max_stare];
int cost[Nmax][Nmax];
///best[i][j] = lant de cost minim intre nodul 0 si nodul i
///care trece prin nodurile a caror indice au valoare 1
///in reprezentarea binara a lui j
//cost[i][j] = costul muchiei (i,j)
vector< int >gt[Nmax];//graful transpus
inline void Citire()
{
    int m , x, y, c;
    ifstream f(In);
    f >> N >> m;
    while( m-- )
    {
        f >> x >> y >> c;
        cost[ x ][ y ] = c;
        gt[y].push_back(x);
    }
    Mstare = (( 1<< N )-1);
    f.close();
}

inline void Dinamica()
{
    int stare, nod, size , i;
    memset(best,Inf,sizeof (best));
    best[0][1] = 0;
    for(stare = 0;stare <= Mstare ;stare++)
        for(nod = 0; nod < N; nod++)
            if(stare & (1<<nod))//daca nodul apartine starii
                for(i = 0, size = gt[nod].size() ; i < size ;i++ )//parcurc lista vecnilor care intra in nod
                    if(stare & (1<<gt[nod][i]))//daca vecinul apartine starii
                        best[nod][stare] = min(best[nod][stare] ,best[gt[nod][i]][stare-(1<<nod)] + cost[gt[nod][i]][nod]);
}

inline void Afisare()
{
    ofstream g(Out);
    int i,sol = Inf,size;
    for(i = 0,size = gt[0].size();i < size ;i++)
        sol = min(sol,best[gt[0][i]][Mstare] + cost[gt[0][i]][0]);
    if(sol==Inf)
        g<<"Nu exista solutie\n";
    else
        g<<sol<<"\n";
    g.close();
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    return 0;
}