#include<fstream>
#include<vector>

using namespace std;
typedef int64_t var;

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

const var MAXN = 18;
const var MAX2N = (1 << MAXN);
const var INF = 10000000001;

var SOL[MAXN][MAX2N];


var n, m;

var C[MAXN][MAXN];
bool G[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(SOL[last][config]) return SOL[last][config];
    var newconf = config - (1 << last);

    if(newconf == 1) {
        SOL[last][config] = C[0][last];
        return SOL[last][config];
    }

    SOL[last][config] = INF;

    for(var v=1; v<n; v++) {
        if(G[v][last] == 0) continue;

        if(config & (1 << v)) {
            var CT = calcul(v, newconf) + C[v][last];
            if(SOL[last][config] > CT) {
                SOL[last][config] = CT;
                //PARENT[last][config] = make_pabefore;
            }
        }
    }
    return SOL[last][config];
}


int main() {
    fin>>n>>m;
    var a, b, c;

    for(var i=0; i<n; i++) {
        for(var j=i; j<n; j++) {
            C[i][j] = C[j][i] = INF;
        }
    }

    while(m--) {
        fin>>a>>b>>c;
        G[a][b] = 1;
        C[a][b] = min(C[a][b], c);
    }

    var end_conf = (1<<n) - 1;
    var min_cost = INF;
    for(var i=0; i<n; i++) {
        if(G[i][0]) {
            min_cost = min(min_cost, calcul(i, end_conf) + C[i][0]);
        }
    }

    if(min_cost == INF) {
        fout<<"Nu exista solutie";
        return 0;
    }

    fout<<min_cost;
    return 0;
}