#include <bits/stdc++.h>
#define oo 1e8

using namespace std;

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

int n, m, answer;

int dp[1<<18][19];
int cost[19][19];

vector <int> graph[19];

int main()
{
    fin>>n>>m;

    for ( int i = 1; i <= m; ++i )
    {
        int first_Node, second_Node;

        fin>>first_Node>>second_Node>>cost[first_Node][second_Node];
        graph[second_Node].push_back(first_Node);
    }

    for ( int i = 2; i < (1<<n); ++i )
        for ( int j = 0; j < n; ++j )
            dp[i][j] = oo;

    for ( int i = 0; i < (1<<n); ++i )
        for ( int j = 0; j < n; ++j )
            if ( i&(1<<j) )
                for ( auto x:graph[j] )
                    if ( i&(1<<x) )
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][x]+cost[x][j]);

    answer = oo;

    for ( int i = 1; i < n; ++i )
        if ( cost[i][0] )
            answer = min(answer, dp[(1<<n)-1][i]+cost[i][0]);

    if ( answer == oo )
        fout<<"Nu exista solutie"<<'\n';
    else
        fout<<answer<<'\n';
}