#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);
	
}
	
 
	
const int INF = 100000000;
	
 
vector <vector <int>> cost, G, dp;
int main() {
	
    int N, M;
	
    fin >> N >> M;
	
    cost.assign(N, vector < int >(N, INF));
    G.resize(N);
    dp.assign(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(int vec : G[node])
	
                    if(mask & (1 << vec))
	
                        min_self(dp[mask][node], dp[mask ^ (1 << node)][vec] + cost[vec][node]);
	
    int ans = INF;
	
    for(int node : G[0])
	
        min_self(ans, dp[(1 << N) - 1][node] + cost[node][0]);
	
    fout << ans;
	
}