#include <bits/stdc++.h>

using namespace std;

const int Nmax = 18;
const int NNmax = ( 1 << 18 );
const int INF = 1e9;

int dp[Nmax][NNmax];
int A[Nmax][Nmax];
int N, M;

int memo( int nodAnterior, int state )
{
    if ( dp[nodAnterior][state] )
        return dp[nodAnterior][state];

    int sol = INF;

    if ( state == ( 1 << N ) - 1 )
    {
        if ( A[nodAnterior][0] )
            sol = A[nodAnterior][0];
    }
    else
    {
        for ( int i = 1; i < N; ++i )
        {
            if ( ( ( state & ( 1 << i ) ) == 0 ) && A[nodAnterior][i] )
            {
                int a = A[nodAnterior][i] + memo( i, state ^ ( 1 << i ) );

                sol = min( sol, a );
            }
        }
    }

    return dp[nodAnterior][state] = sol;
}

int main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");

    in >> N >> M;

    for ( int i = 0, a, b, c; i < M; ++i )
    {
        in >> a >> b >> c;

        A[a][b] = c;
    }

    int sol = memo( 0, 1 );

    if ( sol != INF )
        out << sol << "\n";
    else
        out << "Nu exista solutie\n";

    return 0;
}