#include <fstream>
#include <vector>
#define INF 1 << 20
#define Nmax 20
using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

int n, m, sol, p[ Nmax ];
vector < int > a[ Nmax ], C[ Nmax ];

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

    f >> n >> m;

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

        a[ x ].push_back( y );
        C[ x ].push_back( c );
    }
}

void DFS ( int nod, int nr, int cost )
{
    p[ nod ] = 1;

    for ( int i = 0; i < (int)a[ nod ].size(); ++ i )
    {
        if ( !p[ a[ nod ][ i ] ] )
             DFS( a[ nod ][ i ], nr + 1, cost + C[ nod ][ i ] );

        if ( nr == n && a[ nod ][ i ] == 0 )
             sol = min( INF, cost + C[ nod ][ i ] );
    }

    p[ nod ] = 0;
}

int main()
{
    citire();
    DFS( 0, 1, 0 );

    if ( sol == INF ) g << "Nu exista solutie";
    else g << sol;
    return 0;
}