#include <stdio.h>


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

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

void read_data(FILE *fin,int M)
{
    int i;
    for (i = 1; i <= M; ++i) 
    {
        int x, y, c;

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

        cost[x][y] = c;
    }
}
long min(long x, long y)
{
    if(x>y)
        return y;
    return x;
}
void result(int N)
{
    FILE *fout;
    fout = fopen("hamilton.out", "w");
    int i,x=inf;
    for (i = 0; i < N; ++i)
        if (sol[(1 << N) - 1][i] != inf) 
            x = min(x, sol[(1 << N) - 1][i] + cost[i][0]);
    if (x == inf)
        fprintf(fout, "Nu exista solutie");
    else
        fprintf(fout, "%d", x);
    fclose(fout);
    
}

void matrix_init(int N)
{
    int i,j;
    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;
}
int main() 
{
    FILE *fin;
    fin = fopen("hamilton.in", "r");
    
    int N, M,conf,i,j,bit;
    fscanf(fin, "%d %d", &N, &M);
    
    matrix_init(N);
    read_data(fin,M);

    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]);
            }
        } 
    result(N);
    fclose(fin);

    return 0;
}