#include <fstream>

#include <vector>

#include <iostream>



using namespace std;



const int MAXN = 20;

const int MAXX = 262150;

const int INF = 100000000;

int N, M, Sol;

int Cost[MAXN][MAXN];

int C[MAXX][MAXN];

vector <int> A[MAXN];

int main()

{

    ifstream fin("hamilton.in");

    ofstream fout("hamilton.out");

    fin >> 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)

    {

        int x, y;

        fin >> x >> y;

        A[y].push_back(x);

        fin >> Cost[x][y];

    }

    for (int i = 0; i < 1 << N; ++i)

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

    C[1][0] = 0;

    for (int i = 0; i < 1 << N; ++i)

        for (int j = 0; j < N; ++j)

            if (i & (1<<j))

                for (size_t k = 0; k < A[j].size(); ++k)

                    if (i & (1<<A[j][k]))

                       {

                           C[i][j] = min(C[i][j], C[i ^ (1<<j)][ A[j][k] ] + Cost[ A[j][k] ][j]);

                           //fout<<i<<' '<<j<<' '<<k<<'\n';

                       }

    Sol = INF;

    for (size_t i = 0; i < A[0].size(); ++i)

        Sol = min(Sol, C[(1<<N) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

    if (Sol == INF) fout << "Nu exista solutie" << endl;

    else fout << Sol << endl;

    return 0;

}