#include <fstream>
#include <iostream>
#define MAXN 18
#define INF 100000000
using namespace std;

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

int graph[MAXN][MAXN];
int dp[MAXN][(1 << MAXN)];

int main(){
    int n, m, i, x, y, c, mask, j, sol;
    fin >> n >> m;

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

    for( i = 1; i <= m; i++ ){
        fin >> x >> y >> c;
        graph[x][y] = c;
    }

    for( i = 0; i < n; i++ ){
        for( j = 0; j < (1 << n); j++ )
            dp[i][j] = INF;
    }
    dp[0][1] = 0; //incepem din nodul 0

    for( mask = 0; mask < (1 << n); mask++ ){
        for( i = 0; i < n; i++ ){
            if( mask & (1 << i) ){ //avem nodul i in masca
                for( j = 0; j < n; j++ ){
                    if( graph[j][i] != INF ) //nod de la j la i
                        dp[i][mask] = min( dp[i][mask], dp[j][mask ^ (1 << i)] + graph[j][i] ); //drumul de la 0..i = drumul de la 0 la j + drumul de la j la i
                }
            }
        }
    }

    sol = INF;
    for( i = 0; i < n; i++ )
        sol = min( sol, dp[i][(1 << n) - 1] + graph[i][0]);

    if( sol == INF )
        fout << "Nu exista solutie";
    else
        fout << sol;
    return 0;
}