#include <fstream>
#include <vector>
#include <stack>
#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, answ = INF;
VVI g, c, h;

void Read();

int main()
{
    Read();
    h = VVI(1 << n, VI(n, INF));
    h[1][0] = 0;
    for ( int k = 1; k < 1 << n; ++k )
        for ( int i = 0; i < n; ++i )
            if ( k & (1 << i) )
                for ( const auto& j : g[i] )
                    if ( !( k & (1 << j) ) )
                        h[k | (1 << j)][j] = min(h[k | (1 << j)][j], h[k][i] + c[i][j]);
    for ( int i = 1; i < n; ++i )
        answ = min(answ, h[(1 << n) - 1][i] + c[i][0]);
    if ( answ == INF )
        os << "Nu exista solutie";
    else
        os << answ;
    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;
    }
}