#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 20;
const int INF = 1e9;

vector<int> g[MAXN];

int n, m;
int cost_muchie[MAXN][MAXN];
int cicCostMin[MAXN][1 << MAXN];

int main() {
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        in >> x >> y >> c;
        g[x].push_back(y);
        cost_muchie[x][y] = c;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            cicCostMin[i][j] = INF;
    cicCostMin[0][0] = cicCostMin[0][1] = 0;
    for (int configuratie = 1; configuratie < (1 << n); ++configuratie){
        for (int nod = 0; nod < n; ++nod) {
            if (cicCostMin[nod][configuratie] == INF) continue;
            for (int vecin : g[nod]) {
                if (!(configuratie & (1 << vecin))) {
                    int next_conf = configuratie | (1 << vecin);
                    if (cicCostMin[vecin][next_conf] > cicCostMin[nod][configuratie] + cost_muchie[nod][vecin])
                        cicCostMin[vecin][next_conf] = cicCostMin[nod][configuratie] + cost_muchie[nod][vecin];
                }
            }
        }
    }
    int costul_minim = INF;
    int configuatie_completa = (1 << n) - 1;
    for (int nod = 0; nod < n; ++nod) {
        if (cicCostMin[nod][configuatie_completa] != INF && cost_muchie[nod][0] > 0)
            costul_minim = min(costul_minim, cicCostMin[nod][configuatie_completa] + cost_muchie[nod][0]);
    }
    out << costul_minim;
    return 0;
}