#include <iostream>
#include <fstream>
using namespace std;

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

const int MAXN = 18, INF = 2000000000;

int N, M, edgeCost[MAXN][MAXN], dp[MAXN][ (1<<MAXN) + 1 ];

void citire()
{
    in>>N>>M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        in>>x>>y>>c;
        edgeCost[ x ][ y ] = c;
    }
}

int f(int node, int config)
{
    if( dp[ node ][ config ] != 0 )
        return dp[ node ][ config ];

    if( config == 0 )
    {
        if( edgeCost[ node ][ 0 ] != 0 )
            dp[ node ][ config ] = edgeCost[ node ][ 0 ];
        else
            dp[ node ][ config ] = INF;

        return dp[ node ][ config ];
    }

    dp[ node ][ config ] = INF;

    for(int i = 1; i <= N - 1; i++)
        if( ( (config>>i) & 1 ) == 1 && edgeCost[ node ][ i ] != 0 )
            dp[ node ][ config ] = min( dp[ node ][ config ],
                                        edgeCost[ node ][ i ] + f( i, config^(1<<i) )
                                      );

    return dp[ node ][ config ];
}

int main()
{
    citire();

    int answer = f(0, (1<<N) - 2);

    if( answer == INF )
        out<<"Nu exista solutie";
    else out<<answer;

    return 0;
}