#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;

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

const int INF = 1e9;
int dp[1 << 18][18];
vector<pair<int, int>> g[18];

void solve ()
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int x , y , c ;
        fin >> x >> y >> c ;
        g[y].push_back({x,c}) ;
    }
    for ( int i = 0 ; i <= 1 << n ; i ++ )
        for ( int j = 0 ; j <= n ; j ++ )
            dp[i][j] = INF ;

    dp[1][0] = 0 ;

    for ( int mask = 1 ; mask < ( 1 << n ) ; mask ++ )
        for ( int i = 0 ; i < n ; i ++ )
            if ( mask & ( 1 << i ) )
            {
                for ( auto it : g[i] )
                {
                    int v = it.first ;
                    int c = it.second ;
                    if ( mask & ( 1 << v ) )
                        dp[mask][i] = min ( dp[mask][i] , dp[mask^(1<<i)][v] + c ) ;
                }
            }

    int ans = INF ;
    for ( auto it : g[0] )
    {
        int last_node = it.first ;
        int cost = it.second ;
        ans = min ( ans , dp[(1<<n)-1][last_node] + cost ) ;
    }
    if ( ans == INF )
        fout << "Nu exista solutie" ;
    else
        fout << ans ;

}

int main()
{
    std :: ios_base :: sync_with_stdio ( false ) ;
    fin.tie(0) ;
    fout.tie(0) ;
    solve() ;

    return 0;
}