#include <stdio.h>


#define maxN 20
#define maxConf (1 << 19)
#define inf (1 << 28)

long cost[maxN][maxN], sol[maxConf][maxN];

long min(long x, long y)
{
    if(x>y)
        return y;
    return x;
}
int main() 
{
    FILE *fin, *fout;
    fin = fopen("hamilton.in", "r");

    fout = fopen("hamilton.out", "w");

    int N, M,conf,i,j,bit;

    fscanf(fin, "%d %d", &N, &M);
 

    for (i = 0; i <= N; ++i)
        for (j = 0; j <= N; ++j)
            cost[i][j] = inf;
    for (i = 0; i < (1 << N); ++i)
        for (j = 0; j < N; ++j)
            sol[i][j] = inf;


    for (i = 1; i <= M; ++i) 
    {
        int x, y, c;

        fscanf(fin, "%d %d %d", &x, &y, &c);

        cost[x][y] = c;
    }


    sol[1][0] = 0;


    for (conf = 0; conf < (1 << N); ++conf)
        for (i = 0; i < N; ++i) 
        {
        if (conf & (1 << i))

            for (bit = 0; bit < N; ++bit) 
            {
                if (conf & (1 << bit))

                    if (!(cost[bit][i] == inf))

                          if (!(bit == i))

                                  sol[conf][i] = min(sol[conf][i], sol[conf - (1 << i)][bit] + cost[bit][i]);
            }
        }


    int rsp = inf;

    for (i = 0; i < N; ++i)
        if (sol[(1 << N) - 1][i] != inf) 
            rsp = min(rsp, sol[(1 << N) - 1][i] + cost[i][0]);


    if (rsp == inf)
        fprintf(fout, "Nu exista solutie");
    else
        fprintf(fout, "%d", rsp);
    
    fclose(fin);
    fclose(fout);

    return 0;
}