#include <bits/stdc++.h>
#include <bit>
#define int long long
#define fs first
#define sc second
using namespace std;

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

const int nmx = 20 ;

int g[nmx][nmx] ;
int dp[524300][nmx] ;

signed main()
{
    int n , m ;
    fin >> n >> m ;
    int cvmx = ( 1 << n ) - 1 ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int x , y , c ;
        fin >> x >> y >> c ;
        g[x][y] = c ;
    }
    for ( int i = 1 ; i <= cvmx ; i += 2 )
        for ( int j = 0 ; j < n ; j ++ )
            dp[i][j] = 18000005 ;
    dp[1][0] = 0 ;
    for ( int i = 1 ; i <= cvmx ; i += 2 )
        for ( int j = 0 ; j < n ; j ++ )
            for ( int l = 1 ; l < n ; l ++ )
            {
                if ( g[j][l] != 0 )
                {
                    if ( ( ( i >> l ) & 1 ) == 0 )
                        dp[(i+(1<<l))][l] = min ( dp[(i+(1<<l))][l] , g[j][l] + dp[i][j] ) ;
                }
            }
    int ans = 18000005 ;
    for ( int i = 1 ; i < n ; i ++ )
    {
        if ( g[i][0] != 0 )
            ans = min ( ans , dp[cvmx][i] + g[i][0] ) ;
    }
    if ( ans == 18000005 )
        fout << "Nu exista solutie" ;
    else
        fout << ans ;

    return 0;
}