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

using namespace std;

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

int n, m, answer;
int dp[1<<20][20];
int cost[20][20];

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];
    }

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

    dp[1][0] = 0;

    for ( int i = 1; i < (1<<n); ++i )
        for ( int j = 0; j < n; ++j )
            if ( (i&(1<<j)) )
                for ( int k = 0; k < n; ++k )
                    if ( j != k && i&(1<<k) != 0 && cost[k][j] )
                        dp[i][j] = min (dp[i][j], dp[i^(1<<j)][k]+cost[k][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';
}