#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

inline void min_self(int& a, int b) {
    a = min(a, b);
}

int main() {
    int N, M;
    fin >> N >> M;
    vector < vector < int > > cost(N, vector < int >(N, INF)), G(N), dp(1 << N, vector < int >(N, INF));
    while(M--) {
        int u, v;
        fin >> u >> v >> cost[u][v];
        G[v].emplace_back(u);
    }
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << N); ++mask)
        for(int node = 0; node < N; ++node)
            if(mask & (1 << node))
                for(size_t i = 0; i < G[node].size(); ++i) {
                    int vec = G[node][i];
                    if(mask & (1 << vec))
                        min_self(dp[mask][node], dp[mask ^ (1 << node)][vec] + cost[vec][node]);
                }
    int ans = INF;
    for(size_t i = 0; i < G[0].size(); ++i) {
        int node = G[0][i];
        min_self(ans, dp[(1 << N) - 1][node] + cost[node][0]);
    }
    fout << ans;
}