#include <bits/stdc++.h>
#define int long long

using namespace std;

int dp[2000007][23];
vector<pair<int, int>> adj[23];
int cost[23][23];

signed main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n, m, a, b, val;
    cin>>n>>m;

    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            cost[i][j] = 21e8;

    for(int i=0; i<m; i++)
        cin>>a>>b>>val, adj[a].push_back({b, val}), cost[a][b] = val;

    for(int i=0; i<=(1<<n); i++)
        for(int j=0; j<=n; j++)
            dp[i][j] = 21e8;
    dp[1][0] = 0;

    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
        {
            if((i & (1<<j)) != 0)
                for(auto x : adj[j])
                {
                    int new_nod = x.first, cost = x.second;
                    if((i & (1<<new_nod)) == 0)
                    {
                        int new_mask = i | (1<<new_nod);
                        dp[new_mask][new_nod] = min(dp[new_mask][new_nod], dp[i][j] + cost);
                    }
                }
        }
    }

    int minn = 21e8;
    for(int i=1; i<n; i++)
        if(cost[i][0] != 21e8)
            minn = min(minn, dp[(1<<n) - 1][i] + cost[i][0]);

    cout<<minn;


    return 0;
}