#include <bits/stdc++.h>
#define int long long int
const int inf = 1e12;
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    fin >> n >> m;
    vector<vector<int>> d((n + 1), vector<int>(n + 1, inf));
    for(int i = 1; i <= m; i++)
    {
        int u,v,dist;

        fin >> u >> v >> dist;u++,v++;
        d[u][v] = dist;
    }
    vector<vector<int>> dp((1 << n), vector<int> (n + 1, inf));
    dp[(1 << 0)][1] = 0;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        for(int i = 2; i <= n; i++)
            if(mask & (1 << (i - 1)))
                for(int j = 1; j <= n; j++)
                    if(i != j && d[j][i] != inf && mask &(1 << (j - 1)))
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << (i - 1))][j] + d[j][i]);
    }
    int ans = inf;
    for(int i = 1; i <= n; i++)
        ans = min(ans, dp[(1 << n) - 1][i] + d[i][1]);
    fout <<ans << '\n';
    return 0;
}