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

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

const int INF = 0x3f3f3f3f;
int N, M;
int C[18][18];
int D[1<<18][18];

vector <int> G[18];

int main()
{
    is >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            C[i][j] = INF;
    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 = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;
        G[a].push_back(b);
        C[a][b] = c;
    }
    for (int i = 1; i < (1 << N); ++i)
        for (int j = 0; j < N; ++j)
            if ((i & (1 << j)))
                for (const int& k : G[j])
                    if ( (i & (1 << k)) == 0 && D[i | (1 << k)][k] > D[i][j] + C[j][k])
                        D[i | (1 << k)][k] = D[i][j] + C[j][k];
    int Sol = INF;
    for (int i = 1; i < N; ++i)
        Sol = min(Sol, D[(1<<N)-1][i] + C[i][0]);

    if (Sol == INF) os << "Nu exista solutie";
    else os << Sol;
    is.close();
    os.close();
    return 0;
}