#include <stdio.h>
#define INF 100000000
#define uint unsigned int

uint N, C[18][18], D[131072][18];

void read();
void solve();

int main()
{
    read();
    solve();
    return 0;
}

void solve()
{
    uint i, noduri, j, noduri2, k, min;
    FILE *out;

    for ( i = 1; i <= (1U << (N-1)) - 1; ++i)
    {
        noduri = (i << 1) + 1;
        for ( j = 1; (1U << j) <= noduri; ++j)
            if ((1U << j)  & noduri)
            {
                noduri2 = noduri ^ (1U << j) ;
                min = INF;

                if (noduri2 == 1)
                {
                    if ( C[0][j] )  min = C[0][j];
                }
                else
                {
                    for ( k = 1; (1U << k) <= noduri2; ++k)
                        if ( C[k][j] && ( (1U << k) & noduri2) && min > D[ noduri2 >> 1][k] + C[k][j])
                            min = D[ noduri2 >> 1][k] + C[k][j];
                }

                D[i][j] = min;
            }
    }

    min = INF;
    for (i = 1; i < N; ++i)
        if ( C[i][0] && min > D[ (1U << (N-1)) - 1 ][i] + C[i][0])
            min = D[ (1U << (N-1)) - 1 ][i] + C[i][0];

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

    if(min != INF)  fprintf (out, "%u\n",  min);
    else fprintf (out, "Nu exista solutie\n");

    fclose(out);
}

void read()
{
    FILE *in = fopen("hamilton.in", "r");
    uint e, a, b, c;

    fscanf (in, "%u %u", &N, &e);

    for ( ; e; --e)
    {
        fscanf (in, "%u %u %u", &a, &b, &c);
        C[a][b] = c;
    }

    fclose(in);
}