#include <stdio.h>
#include<limits.h>
#define maxN 20
#define maxConf (1 << 19) 
#define inf (1<<27)
int 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;
    }
}
int min(int x, int 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;
}
void build_matrix(int N)
{
    
    sol[1][0] = 0;
    int conf,bit,i;
    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 main() 
{
    FILE *fin;
    fin = fopen("hamilton.in", "r");   
    int N, M;
    fscanf(fin, "%d %d", &N, &M);
    matrix_init(N);
    read_data(fin,M);
    build_matrix(N);
    result(N);
    fclose(fin);
    return 0;
}