#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int MAXN = 262145;
int dp[MAXN];
vector <int> g[30];
int cost[31][31];
void dfs(int node, int mask){
    for(auto x: g[node]){
        if(!(mask & (1 << x))){
            dp[mask + (1 << x)] = min(dp[mask + (1 << x)], dp[mask] + cost[node][x]);
            dfs(x, mask + (1 << x)) ;
        }
    }
}
int main(){
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= (1 << n); ++i)
        dp[i] = MAXN;
    for(int i = 1; i <= m ; ++i){
        int x, y, cost1;
        fin >> x >> y >> cost1;
        g[x].push_back(y);
        cost[x][y] = cost1;
    }
    dfs(0, 0);
    fout << dp[(1 << (n)) - 1];
    return 0;
}