#include <fstream>
#include <vector>

using namespace std;

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

struct Info {
    int node2;
    int w;
    Info() = default;
    Info(int node2, int w) : node2(node2), w(w) {}
};

int n, m;
vector<vector<Info>> graph, rev_graph;

void read() {
    cin >> n >> m;
    graph.resize(n);
    rev_graph.resize(n);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(Info(b, c));
        rev_graph[b].push_back(Info(a, c));
    }
}

void solve() {
    vector<vector<int>> dp(n, vector<int>(1 << n, 1e9));
    
    dp[0][1] = 0;

    for (int mask = 1; mask < (1 << n); mask ++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                continue;
            }
            for (auto it : rev_graph[i]) {
                dp[i][mask] = min(dp[i][mask], dp[it.node2][mask - (1 << i)] + it.w);
            }
        }
    }

    
    for (auto it : rev_graph[0]) {
        dp[0][(1 << n) - 1] = min(dp[0][(1 << n) - 1], dp[it.node2][(1 << n) - 1] + it.w);
    }

    cout << dp[0][(1 << n) - 1];
}

int main() {

    read();
    solve();
    return 0;
}