#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()

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

template <class TCost>
class Graph {
public:
    struct Edge {
        long from, to;
        TCost cost;
        Edge(long _from, long _to, TCost _cost): from(_from), to(_to), cost(_cost) {};
    };
    long size;
    bool zeroIndexed;
    vector<Edge> edges;
    vector<vector<pair<long, TCost>>> adjacencyList;
    Graph() {};
    Graph(long _size, bool _zeroIndexed = true) {
        zeroIndexed = _zeroIndexed;
        if (!zeroIndexed) _size++;
        size = _size;
        adjacencyList.resize(_size);
    };
    ~Graph() = default;
};
template <class TCost>
class DirectedGraph : public Graph<TCost> {
public:
    using typename Graph<TCost>::Edge;
    vector<vector<Edge>> inEdges;
    DirectedGraph() {};
    DirectedGraph(long _size, bool _zeroIndexed): Graph<TCost>(_size, _zeroIndexed) {};
    DirectedGraph(long _size): Graph<TCost>(_size) {};
    void addEdge(long from, long to, TCost cost = 0) {
        this->edges.push_back({from, to, cost});
        this->adjacencyList[from].push_back({to, cost});
    }
    void printEdges() {
        for (auto edge: this->edges) {
            cout << edge.from << ' ' << edge.to << endl;
        }
    }
    void buildInEdges() {
        inEdges.resize(this->size);
        for (Edge u: this->edges) {
            inEdges[u.to].push_back(u);
        }
    }
};
template <class TCost>
TCost hamiltonPath(DirectedGraph<TCost> graph) {
    // dp vector info[i][j] i bit for path, j last node
    vector<vector<int>> dp(1<<graph.size, vector<int>(graph.size));
    graph.buildInEdges();
    for (int i=1; i<(1<<graph.size); i++) {
        for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
            dp[i][v] = 999999;
        }
    }
    dp[1][0] = 0;
    for (int i=1; i<(1<<graph.size); i++) {
        for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
            if (!(i&(1<<v))) continue;
            for (auto u: graph.inEdges[v]) {
                if (!(i&(1<<u.from))) continue;
                dp[i][v] = min(dp[i][v], dp[(i^(1<<v))][u.from]+(int)u.cost);
            }
        }
    }

    TCost rs = 999999;
    for (auto u:graph.inEdges[0]) {
        rs = min(rs, dp[(1<<graph.size)-1][u.from]+u.cost);
    }

    return rs;
}

int main() {_
    long n,m;
    fi >> n >> m;
    DirectedGraph<long> graph = DirectedGraph<long>(n);
    for (int i=0; i<m; i++) {
        long x,y,v;
        fi >> x >> y >> v;
        graph.addEdge(x,y,v);
    }

    fo << hamiltonPath(graph);

    return 0;
}