#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 18;

int a[N][N], dp[N][1 << N];

int main () {
    
    int n, m, x, y, c;
    
    fin >> n >> m;
    
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < n; j++ )
            a[i][j] = 1e9;
    
    for ( int stare = 0; stare < (1 << n); stare++ )
        for ( int i = 0; i < n; i++ )
            dp[i][stare] = 1e9;
    
    for ( int i = 0; i < m; i++ ) {
        
        fin >> x >> y >> c;
        
        a[x][y] = c;
        a[x][x] = a[y][y] = 0;
    }
    
    dp[0][1] = 0;
    for ( int stare = 0; stare < (1 << n); stare++ )
        for ( int i = 0; i < n; i++ )
            if ( stare & (1 << i) )
                for ( int j = 0; j < n; j++ )
                    if ( !(stare & (1 << j)) )
                        dp[j][stare + (1 << j)] = min ( dp[j][stare + (1 << j)], dp[i][stare] + a[i][j] );
                    
    int ans = 1e9;
    
    for ( int i = 0; i < n; i++ )
        ans = min ( ans, dp[i][(1 << n) - 1] + a[i][0] );
    
    if ( ans == 1e9 )
        fout << "Nu exista solutie";
    else
        fout << ans;
    
    return 0;
}