#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<var> G[MAXN];
var n, m;

var C[MAXN][MAXN];


//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<var>::iterator it = G[last].begin(); it != G[last].end(); ++it) {
        var v = *it;
        if(config & (1 << v)) {
            var CT = calcul(v, newconf) + C[last][v];
            if(SOL[last][config] > CT) {
                SOL[last][config] = CT;
                //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;
        if(C[b][a] == 0) {
            C[b][a] = INF;
            G[b].push_back(a);
        }
        C[b][a] = min(C[b][a], c);
    }

    COMP[0][1] = 1;

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

    fout<<min_cost;
    return 0;
}