#include <fstream>
#include <vector>

using namespace std;

const int INF = 1e9;

int main() {
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    int n, m;
    in >> n >> m;
    vector <vector<int>> c(n, vector<int>(n, INF));
    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        in >> c[x][y];
    }
    in.close();
    vector <vector<int>> cost(1 << n, vector<int>(n, INF));
    cost[1][0] = 0;
    for (int set_i = 3; set_i < (1 << n); set_i += 2) {
        for (int j = 1; j < n; j++) {
            if (set_i & (1 << j)) {
                int set_i_j = (set_i ^ (1 << j));
                for (int k = 0; k < n; k++) {
                    if (set_i_j & (1 << k)) {
                        cost[set_i][j] = min(cost[set_i][j], cost[set_i_j][k] + c[k][j]);
                    }
                }
            }
        }
    }
    int cost_min = INF;
    for (int j = 1; j < n; j++) {
        cost_min = min(cost_min, cost[(1<<n)-1][j] + c[j][0]);
    }
    out << cost_min << "\n";
    out.close();
    return 0;
}