#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 18, MAX_M = MAX_N*(MAX_N-1), INF = 1e9;

const int log[] = {0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4};

FILE *in, *out;

struct graph {

    int lst[MAX_N+1], urm[MAX_M+1], vf[MAX_M+1], cost[MAX_M+1];
    int nr;

    void add(int x, int y, int c)
    {
        urm[++nr] = lst[x];
        vf[nr] = y;
        cost[nr] = c;
        lst[x] = nr;
    }
};

graph g;
int mask;

int d[1<<MAX_N][MAX_N];

int minim(int a, int b)
{
    return (a < b)?a:b;
}

int hamilton(int config, int last)
{
    if(d[config][last] == -1)
    {
        d[config][last] = INF;
        int p = g.lst[last];
        while(p != 0)
        {
            if((config & (1<<(g.vf[p]-1))) != 0)
                if(g.vf[p] != 1 || config == (1<<(last-1))+1)
                    d[config][last] = minim(d[config][last], hamilton(config^(1<<(last-1)), g.vf[p])+g.cost[p]);
            p = g.urm[p];
        }
    }
    return d[config][last];
}

int main()
{
    in = fopen("hamilton.in", "r");
    out = fopen("hamilton.out", "w");

    int n, m;
    int x, y, c;
    int i;
    int minc = INF;
    fscanf(in, "%d%d", &n, &m);

    for(i = 0; i < m; i++)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        x++;
        y++;
        g.add(y,x,c);
    }

    mask = (1<<n)-1;
    int p = g.lst[1];
    memset(d, -1, sizeof(d));
    d[1][1] = 0;
    while(p != 0)
    {
        minc = minim(minc, hamilton(mask, g.vf[p])+g.cost[p]);
        p = g.urm[p];
    }
    if(minc != INF)
        fprintf(out, "%d", minc);
    else fprintf(out, "Nu exista solutie");
    fclose(in);
    fclose(out);
    return 0;
}