#include <fstream>
#include <vector>

using namespace std;

const int Maxn = 20;
const int Maxv = 262150;
const int oo = 1<<30;

int N, M, Sol;
int Cost[Maxn][Maxn];
int C[Maxv][Maxn];
vector <int> Leg[Maxn];

int main()
{
    ifstream F("hamilton.in");
    ofstream G("hamilton.out");

    F >> N >> M;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) Cost[i][j] = oo;

    for (int i = 1; i <= M; ++i)
    {
        int x, y;

        F >> x >> y;
        Leg[y].push_back(x);
        F >> Cost[x][y];
    }

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

    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 < Leg[j].size(); ++k)
                    if (i & (1<<Leg[j][k]))
                        C[i][j] = min(C[i][j], C[i ^ (1<<j)][ Leg[j][k] ] + Cost[ Leg[j][k] ][j]);

    Sol = oo;
    for (size_t i = 0; i < Leg[0].size(); ++i)
        Sol = min(Sol, C[(1<<N) - 1][ Leg[0][i] ] + Cost[ Leg[0][i] ][0]);

    if (Sol == oo)
        G << "Nu exista solutie" << endl;
    else
        G << Sol << endl;
}