#include <fstream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

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

const int INF=1e9;

struct Edge {
    int to;
    int cost;
};

vector<Edge> adj[18];

int dp[1<<18][18];

signed main() {
    int n,m;
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int u,v,c;
        cin>>u>>v>>c;
        adj[u].push_back({v,c});
    }
    int max_mask=1<<n;
    for (int mask=0; mask<max_mask; ++mask) {
        for (int i=0; i<n; ++i) {
            dp[mask][i]=INF;
        }
    }
    dp[1][0]=0;
    for (int mask=1; mask<max_mask; ++mask) {
        for (int i=0; i<n; ++i) {
            if ((mask & (1<<i)) && dp[mask][i]!=INF) {
                for (const auto& edge:adj[i]) {
                    int next_node=edge.to;
                    int cost=edge.cost;
                    if (!(mask & (1<<next_node))) {
                        int next_mask=mask|(1<<next_node);
                        dp[next_mask][next_node]=min(dp[next_mask][next_node],dp[mask][i]+cost);
                    }
                }
            }
        }
    }
    int min_cycle_cost=INF;
    int full_mask=(1<<n)-1;
    for (int i=1; i<n; ++i) {
        if (dp[full_mask][i]!=INF) {
            for (const auto& edge:adj[i]) {
                if (edge.to==0) {
                    min_cycle_cost=min(min_cycle_cost,dp[full_mask][i]+edge.cost);
                }
            }
        }
    }
    cout<<min_cycle_cost<<"\n";
}