#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BIAS 1
#define INF  1000005

int Min(int a, int b)
{
    if(a < b)
        return a;
    
    return b;
}

int main(void)
{
    int i, j, k;
    int n, m;

    FILE* fin = fopen("hamilton.in", "r");
    FILE* fout = fopen("hamilton.out", "w");

    fscanf(fin, "%d %d", &n, &m);

    int** connections = (int**)malloc(sizeof(int*) * (n + BIAS));
    int** values      = (int**)malloc(sizeof(int*) * (n + BIAS));

    int** c           = (int**)malloc(sizeof(int*) * (1 << n));

    for(i = 0; i < n + BIAS; i++)
    {
        connections[i] = (int*)malloc(sizeof(int) * (n + BIAS));
        values[i]      = (int*)malloc(sizeof(int) * (n + BIAS));

        memset(connections[i], 0, sizeof(int) * (n + BIAS));
        for(int j = 0; j < n + BIAS; j++)
            values[i][j] = INF;
    }

    for(i = 0; i < (1 << n); i++)
    {
        c[i] = (int*)malloc(sizeof(int) * n);
        for(j = 0; j < n; j++)
            c[i][j] = INF;
    }

    for(i = 0; i < m; i++)
    {
        int x, y, z;
        fscanf(fin, "%d %d %d", &x, &y, &z);

        connections[y][++connections[y][0]] = x;
        values[x][y] = z;
    }

    c[1][0] = 0;

    for(i = 0; i < (1 << n); i++)
    {
        for(j = 0; j < n; j++)
        {
            if((i >> j) & 1)
            {
                for(k = 1; k <= connections[j][0]; k++)
                {
                    int other = connections[j][k];
                    if((i >> other) & 1)
                    {
                        c[i][j] = Min(c[i][j], c[i ^ (1 << j)][other] + values[other][j]);
                    }
                }
            }
        }
    }

    int firstIndex = (1 << n) - 1;
    int bestSol = INF;

    for(i = 0; i < n; i++)
    {
        if(values[i][0] != INF)
        {
            bestSol = Min(bestSol, c[firstIndex][i] + values[i][0]);
        }
    }

    if(bestSol != INF)
        fprintf(fout, "%d\n", bestSol);
    else
        fprintf(fout, "Nu exista solutie");

    for(i = 0; i < (1 << n); i++)
    {
        free(c[i]);
        c[i] = NULL;
    }

    // I promised I will never give you up, C
    // I'm sorry!
    free(c);
    c = NULL;

    for(i = 0; i < n + BIAS; i++)
    {
        free(values[i]);
        values[i] = NULL;

        free(connections[i]);
        connections[i] = NULL;
    }

    free(values);
    values = NULL;

    free(connections);
    connections = NULL;

    fclose(fout);
    fout = NULL;
    fclose(fin);
    fin = NULL;

    return 0;
}