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


using namespace std;

const int INF = (1 << 30) - 1;


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

class Graph {
private:
    int _n, _m;
    vector<vector<int>> _adjacentList; // liste de adiacenta

    vector<vector<pair<int, int> >> _adjacentListWithCosts;

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void add(); // graf orientat cu costuri

    int hamilton();
};

void Graph::add() {
    int x, y, c;
    _adjacentListWithCosts.resize(_n + 1);

    for (int i = 0; i < _m; ++i) {
        f >> x >> y >> c;
        _adjacentListWithCosts[x].push_back(make_pair(y, c));
    }
}

// Se creeaza matricea costurilor a tuturor drumurilor, care initial e initializata cu INF.
// Se foloseste reprezentarea binara pentru a retine nodurile care fac parte din lant, acestea fiind marcate cu 1
// Pentru fiecare lant, se verifica nodurile care fac parte din acesta si se actualizeaza costul minim
// La final este cautat costul minim al nodurilor care ajung in nodul 0, deoarece cu acesta am inceput
int Graph::hamilton() {
    int answer = INF;
    int nr_nodes = 1 << _n; //numarul de noduri
    int cost[nr_nodes][_n];

    for (int i = 0; i < nr_nodes; ++i)
        for (int j = 0; j < _n; ++j)
            cost[i][j] = INF;

    cost[1][0] = 0;  // fixez nodul de inceput 0, care are costul 0

    for (int i = 0; i < nr_nodes; ++i)
        for (int j = 0; j < _n; ++j)
            if ((i & (1 << j))) {
                for (int k = 0; k < _adjacentListWithCosts[j].size(); ++k) {

                    if (i & (1 << _adjacentListWithCosts[j][k].first)) {
                        cost[i][j] = min(cost[i][j], cost[i ^ (1 << j)][_adjacentListWithCosts[j][k].first] +
                                                     _adjacentListWithCosts[j][k].second);
                    }
                }
            }

    for (int i = 0; i < _adjacentListWithCosts[0].size(); ++i)
        answer = min(answer, cost[nr_nodes - 1][_adjacentListWithCosts[0][i].first] +
                             _adjacentListWithCosts[0][i].second);

    return answer;
}

int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.add();
    int answer = gr.hamilton();
    g << answer;

    f.close();
    g.close();
    return 0;
}