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

#define BIAS  1
#define TRUE  1
#define FALSE 0

typedef char byte;

int   n, m;
int** valuesMatrix;
int** neighbourMatrix;

int   firstNode;
int   minValue = -1;
byte* nodeInUse;

void DFS(int startPos, int indexSol, int val)
{
    if(!nodeInUse[startPos])
    {
        nodeInUse[startPos] = TRUE;

        if(indexSol >= (n - 1))
        {
            if(valuesMatrix[startPos][firstNode])
            {
                val += valuesMatrix[startPos][firstNode];
                if(minValue == -1 || minValue > val)
                {
                    minValue = val;
                }
            }
        }
        else
        {
            for(int i = 1; i <= neighbourMatrix[startPos][0]; i++)
            {
                int other = neighbourMatrix[startPos][i];
                int newVal = val + valuesMatrix[startPos][other];

                if(minValue == -1 || minValue > newVal)
                {
                    DFS(other, indexSol + 1, newVal);
                }
            }
        }
        

        nodeInUse[startPos] = FALSE;
    }
}

int main(void)
{
    FILE* fin  = fopen("hamilton.in", "r");
    FILE* fout = fopen("hamilton.out", "w");
    
    fscanf(fin, "%d %d", &n, &m);

    valuesMatrix    = (int**)malloc(sizeof(int*) * (n + BIAS));
    neighbourMatrix = (int**)malloc(sizeof(int*) * (n + BIAS));

    nodeInUse       = (byte*)malloc(sizeof(byte) * (n + BIAS));
    
    for(int i = 0; i < (n + BIAS); i++)
    {
        valuesMatrix[i]    = (int*)malloc(sizeof(int) * (n + BIAS));
        neighbourMatrix[i] = (int*)malloc(sizeof(int) * (n + BIAS));

        memset(valuesMatrix[i],    NULL, sizeof(int) * (n + BIAS));
        memset(neighbourMatrix[i], NULL, sizeof(int) * (n + BIAS));
    }

    memset(nodeInUse, FALSE, sizeof(byte) * (n + BIAS));

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

        valuesMatrix[x][y] = c;
        neighbourMatrix[x][++neighbourMatrix[x][0]] = y;
    }

    for(int i = 0; i < n; i++)
    {
        firstNode = i;
        DFS(i, 0, 0);
    }

    if(minValue != -1)
        fprintf(fout, "%d\n", minValue);
    else
        fprintf(fout, "Nu exista solutie");
    
    free(nodeInUse);
    nodeInUse = NULL;

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

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

    free(neighbourMatrix);
    neighbourMatrix = NULL;

    free(valuesMatrix);
    valuesMatrix = NULL;
        
    fclose(fout);
    fout = NULL;

    fclose(fin);
    fin = NULL;

    return 0;
}