#include <bits/stdc++.h>

using namespace std;

const char inputFile[] = "hamilton.in";
const char outputFile[] = "hamilton.out";

ifstream in(inputFile);
ofstream out(outputFile);

typedef unsigned short ushort;
typedef unsigned long long ullong;

ushort N, M;
ullong cmin, cost;
bool gasit;

vector<vector<ullong>> mat;
vector<ushort> sol;
vector<bool> car;

bool ebun(ushort k)
{
    return mat[sol[k - 1]][sol[k]];
}

bool esol(void)
{
    return mat[sol[N]][sol[1]]; /// return mat[sol[N]][0];
}

void back(ushort k)
{
    for(ushort i = 1; i < N; ++i)
    {
        sol[k] = i;
        if(!car[i] && ebun(k) && (!gasit || cost < cmin))
        {
            cost += mat[sol[k - 1]][sol[k]];
            car[i] = true;
            if(k == N && esol())
            {
                cost += mat[sol[N]][sol[1]];
                if(!gasit)
                {
                    gasit = true;
                    cmin = cost;
                }
                else cmin = min(cmin, cost);
                cost -= mat[sol[N]][sol[1]];
            }
            else if(k < N)
                back(k + 1);
            car[i] = false;
            cost -= mat[sol[k - 1]][sol[k]];
        }
    }
}

int main(void)
{
    in >> N >> M;
    mat.resize(N);
    for(ushort i = 0; i < N; ++i)
    {
        mat[i].resize(N);
        mat[i].assign(N, 0);
    }
    for(ushort i = 0; i < M; ++i)
    {
        ushort x, y;
        ullong c;
        in >> x >> y >> c;
        mat[x][y] = c;
    }
    car.resize(N);
    car.assign(N, false);
    car[0] = true;
    sol.resize(N + 1);
    sol[1] = 0;
    back(2);
    if(!gasit)
        out << "Nu exista solutie";
    else out << cmin;
    return 0;
}