#include <stdio.h>
#include <vector>

#define NMAXX 18
#define INF 1000000000

using namespace std;

vector <int> graph[NMAXX];
int dp[NMAXX][1 << NMAXX], cost[NMAXX][NMAXX];

int main()
{
    FILE *fin, *fout;
    int n, m, i, a, b, c, mask, minn, j;

    fin = fopen( "hamilton.in", "r" );
    fout = fopen( "hamilton.out", "w" );

    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        graph[a].push_back( b );
        cost[a][b] = c;
    }

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

    for ( i = 0; i < (1 << n); i++ )
        for ( j = 0; j < n; j++ )
            dp[j][i] = INF;

    dp[0][1] = 0;
    for ( mask = 0; mask < (1 << n); mask++ )
        for ( i = 0; i < n; i++ )
            if ( (mask & (1 << i)) != 0 )
                for ( int j : graph[i] )
                    if ( (mask & (1 << j)) != 0 )
                        dp[j][mask] = min( dp[j][mask], dp[i][mask - (1 << j)] + cost[i][j] );

    minn = INF;
    for ( i = 0; i < n; i++ ) {
        minn = min( minn, dp[i][(1 << n) - 1] + cost[i][0] );
    }

    if ( minn != INF )
        fprintf( fout, "%d", minn );
    else
        fprintf( fout, "Nu exista solutie" );

    fclose( fin );
    fclose( fout );
    return 0;
}