#include <bits/stdc++.h>
#define NMAX 18

using namespace std;

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

typedef unsigned short ushort;

ushort N, M, sol[NMAX + 1];
unsigned a[NMAX][NMAX], cmin;
bool e;

unsigned cc(ushort k);

bool ebun(ushort k)
{
    if(k == 1)
        return true;
    for(ushort i = 1; i < k; ++i)
        if(sol[i] == sol[k])
            return false;
    if(cc(k) + N - k + 1 >= cmin && e)
        return false;
    if(k == N)
        return a[sol[N - 1]][sol[N]] && a[sol[N]][sol[1]];
    return a[sol[k - 1]][sol[k]];
}

unsigned f()
{
    unsigned sum = 0;
    for(ushort i = 2; i <= N; ++i)
        sum += a[sol[i - 1]][sol[i]];
    return sum + a[sol[N]][sol[1]];
}

unsigned cc(ushort k)
{
    unsigned sum = 0;
    for(ushort i = 2; i <= k; ++i)
        sum += a[sol[i - 1]][sol[i]];
    return sum;
}

void back(ushort k)
{
    for(ushort i = 0; i < N; ++i)
    {
        sol[k] = i;
        if(ebun(k))
        {
            if(k == N)
            {
                if(!e)
                {
                    e = true;
                    cmin = f();
                }
                else cmin = min(cmin, f());
            }
            else back(k + 1);
        }
    }
}

int main()
{
    in >> N >> M;
    for(ushort i = 1; i <= M; ++i)
    {
        ushort x, y;
        unsigned cost;
        in >> x >> y >> cost;
        a[x][y] = cost;
    }
    back(1);
    if(!e)
        out << "Nu exista solutie";
    else out << cmin;
    return 0;
}