#include <cstdio>
#include <vector>
#include <cstring>
#define nMax 19
#define inf 200000000
#define min(a,b) ((a<b)?a:b)

using namespace std;

vector <int> graf[nMax];
int cost[nMax][nMax];
int sol[1 << (nMax - 1) + 5][nMax];
int n;
int s;

void citire()
{
    int m;
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < n; ++ i){
        for (int j = 0; j < n; ++ j){
            cost[i][j] = inf;
        }
    }
    while (m --){
        int x;
        int y;
        scanf ("%d %d", &x, &y);
        graf[y].push_back (x);
        scanf ("%d", &cost[x][y]);
    }
    m = 1 << n ;
    for (int i = 0; i <= m; ++ i){
        for (int j = 0; j < n; ++ j){
            sol[i][j] = -1;
        }
    }
}


int fct (int inceput, int sfarsit)
{
    if (sol[inceput][sfarsit] != -1){
        return sol[inceput][sfarsit];
    }
    sol[inceput][sfarsit] = inf;
    for (unsigned int i = 0; i < graf[sfarsit].size(); ++ i){
        if (inceput & (1<<graf[sfarsit][i]) ){
            if (graf[sfarsit][i] == 0 && inceput != (1<<sfarsit) + 1 ){
                continue;
            }
            sol[inceput][sfarsit] = min (sol[inceput][sfarsit],
                                         fct (inceput ^ (1<<sfarsit), graf[sfarsit][i]) +
                                         cost [graf[sfarsit][i]][sfarsit]);
        }
    }
    return sol[inceput][sfarsit];
}

void rezolvare()
{
    s = inf;
    sol[1][0] = 0;
    for (unsigned int i = 0; i < graf[0].size(); ++ i){
        s = min (s, fct((1 << n) - 1, graf[0][i]) + cost[graf[0][i]][0]);
    }
    if (s == inf){
        printf ("Nu exista solutie\n");
        return;
    }
    printf ("%d\n", s);
}

int main()
{
    freopen ("hamilton.in", "r", stdin);
    freopen ("hamilton.out", "w", stdout);

    citire();
    rezolvare();

    return 0;
}