#include <cstdio>
#include <vector>
#define BIT(x) (1<<x)
#define inf 1000000000
#define min(x,y) (x<y?x:y)

using namespace std;

struct Muchie
{
    int catre, cost;
};

vector<Muchie> v[18];

FILE* fin = freopen("hamilton.in", "r", stdin);
FILE* fout = freopen("hamilton.out", "w", stdout);

int mat[18][BIT(18)];
int n, nm;

int solve()
{
    int i, j, k, a, b, c;
    scanf("%d%d", &n, &nm);
    for(i = 0; i < nm; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        v[b].push_back(Muchie());
        v[b].back().catre = a;
        v[b].back().cost = c;
    }
    for(i = 0; i < n; i++)
        for(j = 0; j < BIT(n); j++)
            mat[i][j] = inf;
    mat[0][1] = 0;
    for(j = 3; j < BIT(n); j += 2)
    {
        for(i = 1; i < n; i++)
        {
            if((j & BIT(i)) == 0)
                continue;
            mat[i][j] = inf;
            for(k = 0; k < v[i].size(); k++)
            {
                if((j & BIT(v[i][k].catre)) != 0)
                {
                    mat[i][j] = min(mat[i][j], mat[v[i][k].catre][j - BIT(i)] + v[i][k].cost);
                }
            }
        }
    }
    int sol = inf;
    for(i = 0; i < v[0].size(); i++)
    {
        sol = min(sol, mat[v[0][i].catre][BIT(n) - 1] + v[0][i].cost);
    }
    return sol;
}

int gsol = solve();

int main()
{
    if(gsol >= inf) printf("Nu exista solutie");
    else printf("%d", gsol);
}