#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int inf = 1e9;
int n, m;
vector<vector<int>> dp, dist;
void hamil()
{
    dp[(1 << 0)][0] = 0;
    for(int mask = 0; mask < (1 << n); mask ++)
        if(mask & (1 << 0))
            for(int i = 1; i < n; i ++)
                if(mask & (1 << i))
                    for(int j = 0; j < n; j ++)
                        if((mask & (1 << j)) && i != j)
                            dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
    int ans = inf;
    for(int i = 1; i < n; i ++)
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    cout << ans;
}
int32_t main()
{
    cin >> n >> m;
    dist.assign(n + 5, vector<int>(n + 5, inf));
    dp.assign((1 << n) + 5, vector<int>(n + 5, inf));
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        dist[x][y] = z;
    }

    hamil();
    return 0;
}