#include <bits/stdc++.h>
#define INFINIT 280000000

int cost[18][18], d[263000][18];

int min( int a, int b ) {
    return a < b ? a : b;
}

int main() {
    FILE *fin, *fout;
    int n, m, i, a, b, c, j, ii, k, mn;
    fin = fopen( "hamilton.in", "r" );
    fout = fopen( "hamilton.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
            if ( i != j )
                cost[i][j] = INFINIT;
    for ( i = 0; i < ( 1 << n ); i++ )
        for ( j = 0; j < n; j++ )
            d[i][j] = INFINIT;
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        cost[a][b] = c;
    }
    d[1][0] = 0;
    for ( i = 3; i < ( 1 << n ); i+=2 ) {
        for ( j = 0; j < n; j++ ) {
            ii = i ^ ( 1 << j );
            for ( k = 0; k < n; k++ ) {
                if ( ( 1 << k )&ii && k != j ) {
                    d[i][j] = min( d[i][j], d[ii][k] + cost[k][j] );
                }
            }
        }
    }
    mn = INFINIT;
    for ( j = 0; j < n; j++ ) {
        if ( mn > d[1 << n - 1][j] + cost[j][0] ) //Stefan was here
            mn = d[1 << n - 1][j] + cost[j][0];
    }
    if ( mn >= INFINIT )
        fprintf( fout, "Nu exista solutie" );
    else
        fprintf( fout, "%d", mn );
    fclose( fin );
    fclose( fout );
    return 0;
}