#include <iostream>
#include <fstream>

using namespace std;

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

const int INF = 0x3f3f3f3f;

int N, M, ANS, x, y;
int Cost[19][19],D[300000][19];

int main()
{

    in >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            Cost[i][j] = INF;

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

    for (int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++)
            D[i][j] = INF;

    D[1][0] = 0;
    for (int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++)
            if (i & (1<<j))
                for (int k = 0; k < N; k++)
                    if (i & (1<<k))
                        D[i][j] = min (D[i][j],D[i^(1<<j)][k] + Cost[k][j]);

    ANS = INF;
    for (int i = 0; i < N; i++)
        if (D[(1<<N) - 1][i] + Cost[i][0] < ANS)
            ANS = D[(1<<N) - 1][i] + Cost[i][0];


    if (ANS == INF)
        out << "Nu exista solutie\n";
    else
        out << ANS;
    return 0;

}