#include <cstdio>
#include <algorithm>
#include <vector>

#define DIM 20
#define INF (1<<29)
using namespace std;

int N, M, X, Y, cost, minim;
int Cost[DIM][DIM];
int D[(1<<DIM)][DIM];
vector <int> Edges[DIM];

int main () {

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

    scanf ("%d %d", &N, &M);

    for (int i = 1; i <= M; i ++) {
        scanf ("%d %d %d", &X, &Y, &cost);

        Edges[X].push_back(Y);
        Cost[X][Y] = cost;
    }

    for (int i = 0; i < (1<<N); i ++)
        for (int j = 0; j < N; j ++)
            D[i][j] = INF;
    D[1][0] = 0;

    for (int i = 1; i < (1<<N); i ++) {
        for (int j = 0; j < N; j ++) {

            vector <int> :: iterator it;
            for (it = Edges[j].begin(); it != Edges[j].end(); it ++) {
                int k = *it;

                if (((i>>k)&1) == 0)
                    D[i+(1<<k)][k] = min (D[i+(1<<k)][k], D[i][j] + Cost[j][k]);
            }
        }
    }

    minim = INF;
    for (int i = 1; i < N; i ++) {

        vector <int> :: iterator it;
        for (it = Edges[i].begin(); it != Edges[i].end(); it ++) {
            int j = *it;

            if (j == 0)
                minim = min (minim, D[(1<<N)-1][i] + Cost[i][j]);
        }
    }

    printf ("%d\n", minim);

    fclose (stdin );
    fclose (stdout);

    return 0;
}