#include <cstdio>
#include <vector>

using namespace std;

const long N = 20, Config = 270000, INF = 1 << 30;
long n, m, c [N][N], dp [Config][N], lim;
vector <long> v [N];

void initCost (){
    long i, j;
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
            c [i][j] = INF;
}

void init (){
    long i, j;
    for (i = 0; i < lim; i ++) {
        for (j = 0; j < n; j ++)
            dp [i][j] = INF;
    }
    for (i = 0; i < n; i ++)
        dp [1 << i][i] = 0;
}

void read (){
    long i, x, y, c1;
    scanf ("%ld%ld", &n, &m);
    initCost ();
    for (i = 0; i < m; i ++){
        scanf ("%ld%ld%ld", &x, &y, &c1);
        c [x][y] = c1;
        v [y].push_back(x);
    }
}

long DP (long config, long x){
    long j, k;
    vector <long> :: iterator it;
    if (dp [config][x] == INF){
        for (it = v [x].begin(); it != v [x].end (); ++ it)
            if (config & (1 << (*it))) {
                if (!((*it) == 0 && config != ((1 << x) + 1))){
                    k = DP (config ^ (1 << x), *it) + c [*it][x];
                    if (k < dp [config][x])
                        dp [config][x] = k;
                }
            }
    }
    return dp [config][x];
}

long cicluHamiltonianMin(){
    long k, min = INF, configFinal;
    vector <long> :: iterator it;
    // nodul start = 0
    configFinal = (1 << n) - 1;
    for (it = v [0].begin (); it != v [0].end (); ++ it){
        k = DP (configFinal, *it) + c [*it][0];
        if (k < min)
            min = k;
    }
    return min;
}

int main () {
    long min;

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

    read ();
    lim = 1 << n;
    init ();
    min = cicluHamiltonianMin ();
    printf ("%ld\n", min);
    return 0;
}