#include <bits/stdc++.h>
#define Nmax 20
#define Mmax (1<<18) + 1
using namespace std;

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

struct graf
{
    graf* next;
    int nod, cost;
};

graf* v[Nmax];

int cost[Mmax][Nmax];

const int INF = 2000000;
int n,m;

void read ( );

void min_Hamilton();

int main()
{
    read ( );

    min_Hamilton();

    return 0;
}

void min_Hamilton()
{
    int nr_combinatii = 1 << n;

    for ( int i = 1; i < nr_combinatii; i++ )
        for ( int j = 0; j < n; j++ )
            cost[i][j] = INF;

    cost[1][0] = 0;

    graf* q;

    for ( int i = 1; i < nr_combinatii; i++ )
        for ( int j = 0; j < n; j++ )
            if ( i & (1<<j) )
            {
                q = v[j];

                while ( q )
                {
                    if ( i & (1 << ( q -> nod ) ) )
                        cost[i][j] = min( cost[i][j], cost[ i ^ (1 << j)  ][q->nod] + q->cost );

                    q = q->next;
                }
            }

    int sol = INF;

    q = v[0];

    while ( q )
    {
        sol = min ( sol, cost[(1<<n) - 1][q->nod] + q->cost );
        q = q->next;
    }

    if ( sol == INF )
        fout << "Nu exista solutie\n";

    else fout << sol;
}

void add ( int x, int y, int c )
{
    graf* node = new graf;

    node -> next = v[x];
    node -> nod = y;
    node -> cost = c;

    v[x] = node;

    return ;
}

void read ( )
{
    int x, y, c;

    fin >> n >> m;

    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y >> c;

        add ( x, y,c );
    }
}