#include <fstream>
#include <vector>

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

const int NMAX = 18;
const int INF = 1<<30;

std::vector <int> edges[1 + NMAX];
int cost[1 + NMAX][1 + NMAX];
int sol[1 + NMAX][1 + ( 1 << NMAX )];

int solve ( int x, int val ) {
    if ( sol[x][val] )
        return sol[x][val];
    sol[x][val] = INF;
    for ( int i = 0; i < edges[x].size(); ++i ) {
        int newNode = edges[x][i];
        if ( val & ( 1 << ( x - 1 ) ) )
            sol[x][val] = std::min ( sol[x][val], std::min ( INF, solve ( newNode, val ^ ( 1 << ( x - 1 ) ) ) + cost[newNode][x] ) );
    }
    return sol[x][val];
}

int main() {
    int N, M;

    fin >> N >> M;

    for ( int i = 1; i <= M; ++i ) {
        int x, y, c;
        fin >> x >> y >> c;
        edges[y].push_back ( x );
        cost[x][y] = c;
    }

    for ( int i = 0; i < N - 1; ++i )
        sol[i + 1][1 << i] = cost[0][i + 1];

    int ans = INF;
    for ( int i = 0; i < edges[0].size(); ++i ) 
        ans = std::min ( ans, std::min ( INF, solve ( edges[0][i], ( 1 << ( N - 1 ) ) - 1 ) + cost[edges[0][i]][0] ) );
    
    if ( ans == INF )
        fout << "Nu exista solutie";
    else
        fout << ans;
    
    fin.close();
    fout.close();
    
    return 0;
}