#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 ( );

void min_Hamilton();

int main()
{
    read ( );

    min_Hamilton();

    return 0;
}

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

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

    cost[1][0] = 0;

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

                for ( int k = 0; k < lng; k++ )
                    if ( i & ( 1 << v[j][k]) )
                    cost[i][j] = min ( cost[i][j], cost[i ^ (1<<j) ][v[j][k]] + a[v[j][k]][j] );
            }

    int sol = INF;

    lng = v[0].size();

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

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

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

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;
    }
}