#include <fstream>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;

int n, m;
VVI g, c, q;

void Read();

int main()
{
    Read();
    q = VVI(1 << n, VI(n, INF));
    q[1][0] = 0;
    for ( int k = 1; k < 1 << n; ++k )
        for ( int i = 0; i < n; ++i )
        {
            if ( !( k & (1 << i) ) )
                continue;
            for ( const auto& j : g[i] )
            {
                if ( ( k & (1 << j) ) )
                    continue;
                q[k | (1 << j)][j] = min(q[k | (1 << j)][j], q[k][i] + c[i][j]);
            }
        }
    int answ = INF;
    for ( int i = 0; i < n; ++i )
        answ = min(answ, q[(1 << n) - 1][i] + c[i][0]);
    if ( answ != INF )
        os << answ;
    else
        os << "Nu exista solutie";
    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n >> m;
    g = VVI(n);
    c = VVI(n, VI(n, INF));
    int n1, n2, cost;
    while ( m-- )
    {
        is >> n1 >> n2 >> cost;
        g[n1].push_back(n2);
        c[n1][n2] = cost;
    }
}