#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;

char rax, neg;
void read(int& v)
{
    neg = 0;
    while((fread(&rax, 1, 1, fin)) && rax != '-' && (rax < '0' || rax > '9'));
    if(rax == '0') { neg = 1; v = 0; }
    else v = rax - '0';
    while((fread(&rax, 1, 1, fin)) && rax >= '0' && rax <= '9') v = v * 10 + rax - '0';
}

int main()
{
    int i, j, k, a, b, c;
    read(n); read(nm);
    for(i = 0; i < nm; i++)
    {
        read(a); read(b); read(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);
    }
    if(sol >= inf) printf("Nu exista solutie");
    else printf("%d", sol);
    return 0;
}