#include <bits/stdc++.h>

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

const int NMAX = 18;

vector<pair<int, int>> adj[NMAX];
int dp[NMAX + 1][(1 << NMAX) + 10];

int main()
{
    
    int n, m;
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost}); //arc x -> y;
        
    }
    
    for(int i=0; i<n; i++)
        for(int j=0; j<(1 << n); j++)
            dp[i][j] = 2e9;
    
    for(int i=0; i<n; i++)
        dp[i][(1 << i)] = 0;
        
    for(int config=0; config<(1 << n); config ++){
        
        for(int i=0; i<n; i++){
            
            if(dp[i][config] != 2e9){
                
                for(auto next : adj[i]){
                    
                    if((config & (1 << next.first)) == 0){
                        
                        dp[next.first][config + (1 << next.first)] = min(dp[next.first][config + (1 << next.first)], dp[i][config] + next.second);
                        
                    }
                    
                }
                
            }
            
        }
        
    }
    
    int mn = 2e9;
    
    for(int i=1; i<n; i++){
        
        for(auto next : adj[i])
            if(next.first == 0)
              mn = min(mn, dp[i][(1 << n) - 1] + next.second);
        
    }
       // cout << dp[i][(1 << n) - 1] << endl;
    g << mn;
    return 0;
}