#include <bits/stdc++.h>
#define Nmax 20
#define Mmax 262150
using namespace std;

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

vector < int > v[Nmax];
int a[Nmax][Nmax];
int cost[Mmax][Nmax];

const int INF = 100000000;
int n,m;

void read ( );

int min_Hamilton( int, int );

int main()
{
    read ( );

    int sol = INF, lng;

    lng = v[0].size();

    for ( int i = 0; i < lng ; i++ )
        sol = min ( sol, min_Hamilton( (1<<n) - 1, v[0][i] ) + a[v[0][i]][0]);

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

    else
        fout << sol << '\n';

    return 0;
}

int min_Hamilton( int conf, int last)
{
    if ( cost[conf][last] == -1 )
    {
        int lng = v[last].size();

        cost[conf][last] = INF ;

        for ( int i = 0; i < lng ; i++ )
            if ( conf & (1<<v[last][i]) )
            {
                if ( v[last][i] == 0 && conf != ( 1 << last ) + 1  )
                    continue;

                cost[conf][last] = min ( cost[conf][last], min_Hamilton( conf ^ (1 << last ), v[last][i] ) + a[v[last][i]][last]);
            }
    }

    return cost[conf][last];
}

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

    fin >> n >> m;

    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < n; j++ )
            a[i][j] = INF;

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

        v[y].push_back( x );

        a[x][y] = c;
    }

    memset(cost, -1, sizeof (cost) );

    cost[1][0] = 0;
}