#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int n,c;
};

const int INF = 99999999;
int cost[18][18];
int dp[1<<18][18];

signed main()
{
    ifstream fin ("hamilton.in");
    ofstream fout ("hamilton.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n,m; fin>>n>>m;
    if(n == 1)
    {
        fout<<'0';
        return 0;
    }
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cost[i][j] = INF;
    for(int i=0; i<m; ++i)
    {
        int a,b,c; fin>>a>>b>>c;
        cost[a][b] = c;
    }
    vector<int> vec(1<<n);
    for(int i=0; i<(1<<n); ++i)
        vec[i] = i;
    sort(vec.begin(), vec.end(), [](const int &a, const int &b){return __builtin_popcount(a) < __builtin_popcount(b);});
    for(int i=0; i<(1<<n); ++i)
        for(int j=0; j<n; ++j)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for(auto &mask : vec)
    {
        if(!(mask & 1)) continue;
        for(int p=0; p<n; ++p)
            if(mask & (1<<p))
            {
                for(int q=0; q<n; ++q)
                    if(p != q && mask & (1<<q))
                        dp[mask][p] = min(dp[mask][p], dp[mask ^ (1<<p)][q] + cost[q][p]);
//                cout<<bitset<5>(mask).to_string()<<' '<<p<<' '<<dp[mask][p]<<'\n';
            }
    }
    int res = INF;
    for(int i=0; i<n; ++i)
        res = min(res, dp[(1<<n)-1][i] + cost[i][0]);
    fout<<res;
    return 0;
}