#include<fstream>
#include<vector>

using namespace std;
typedef int64_t var;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const var MAXN = 19;
const var MAX2N = (1 << (MAXN - 1)) + 1;
const var INF = 10000000001;

var SOL[MAXN][MAX2N];
bool COMP[MAXN][MAX2N];

struct Edge {
    var n, c;
    Edge(var a, var b) {
        n = a;
        c = b;
    }
    Edge(){}
};

vector<Edge> G[MAXN];
var n, m;


//Calculeaza costul minim pentru a realiza configuratia config cu ultimul nod pe poz last
//Asta este egala cu min{calcul(v, config-2^last) + cost(v, last)} , unde v apartine Adj(last)
var calcul(var last, var config) {
    if(COMP[last][config]) return SOL[last][config];

    var newconf = config - (1 << last);

    SOL[last][config] = INF;

    for(vector<Edge>::iterator it = G[last].begin(); it != G[last].end(); ++it) {
        var v = (*it).n;
        if(config & (1 << v)) {
            var C = calcul(v, newconf) + (*it).c;
            if(SOL[last][config] > C) {
                SOL[last][config] = C;
                //PARENT[last][config] = make_pabefore;
            }
        }
    }
    COMP[last][config] = 1;
    return SOL[last][config];
}


int main() {
    fin>>n>>m;
    var a, b, c;
    while(m--) {
        fin>>a>>b>>c;
        G[b].push_back(Edge(a, c));
    }

    for(var i=0; i<n; i++) {
        COMP[i][0] = 1;
        COMP[0][1] = 1;
    }

    var end_conf = (1<<n) - 1;
    var min_cost = INF;
    for(vector<Edge>::iterator it = G[0].begin(); it != G[0].end(); ++it) {
        min_cost = min(min_cost, calcul((*it).n, end_conf) + (*it).c);
    }

    fout<<min_cost;
    return 0;
}