#include <cstdio>
#include <algorithm>
#include <vector>
#define nod first
#define cost second
using namespace std;

const int NMAX = 19, INF = 2e9;

vector <pair <int, int> > G[NMAX];
int D[1 << NMAX][NMAX];

int main () {

    freopen ("hamilton.in", "r", stdin);
    freopen ("hamilton.out", "w", stdout);
    vector <pair <int, int> > :: iterator k;
    int N, M, i, j, a, b, c;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d%d", &a, &b, &c),
        G[b].push_back (make_pair (a, c));
    a = 1 << N;
    for (i = 0 ; i < a; ++i)
        for (j = 0; j <= N; ++j)
            D[i][j] = INF;
    D[1][0] = 0;
    for (i = 0; i < a; ++i)
        for (j = 0; j < N; ++j)
            if (i & (1 << j))
                for (k = G[j].begin (); k != G[j].end (); ++k)
                    if (i & (1 << k->nod))
                        D[i][j] = min (D[i][j], D[i ^ (1 << j)][k->nod] + k->cost);
    b = INF;
    for (k = G[0].begin (); k != G[0].end (); ++k)
        b = min (b, D[a - 1][k->nod] + k->cost);
    printf ("%d", b);

}