#include <cstdio>

#define sqrInf 99999999

using namespace std;

FILE *f, *g;

int n, m;

int lst[20];

int urm[400];
int nod[400];
int cost[400];

int k;

int rez;

int a[300001][20];

inline int mna(int a, int b)
{
    return (a < b ? a : b);
}

void add(int a, int b, int c)
{
    k ++;

    nod[k] = b;
    cost[k] = c;
    urm[k] = lst[a];

    lst[a] = k;
}

void readFile()
{
    f = fopen("hamilton.in", "r");

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

    int i;
    int a, b, c;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d%d", &a, &b, &c);

        add(b, a, c);
    }

    fclose(f);
}

void solve()
{
    rez = sqrInf;

    int i, j, p;

    for(i = 0; i <= (1 << n) - 1; i ++)
    {
        for(j = 0; j < n; j ++)
            a[i][j] = sqrInf;
    }

    a[1][0] = 0;

    for(i = 3; i <= (1 << n) - 1; i += 2)
    {
        for(j = 1; j < n; j ++)
        {
            if((i & (1 << j)) != 0)
            {
                for(p = lst[j]; p != 0; p = urm[p])
                {
                    a[i][j] = mna(a[i][j], a[i - (1 << j)][nod[p]] + cost[p]);
                }
            }
        }
    }

    for(p = lst[0]; p != 0; p = urm[p])
        rez = mna(rez, a[(1 << n) - 1][nod[p]] + cost[p]);
}

void printFile()
{
    g = fopen("hamilton.out", "w");

    if(rez == sqrInf)
        fprintf(g, "Nu exista solutie");

    else
        fprintf(g, "%d\n", rez);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}