#include <fstream>

using namespace std;

const int INF = 2 * 1e9 + 1;
int cost[18][18];
int dp[(1 << 18) + 1][18];

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        cost[u][v] = w;
    }
    for (int mask = 1; mask < (1 << n); mask++)
    {
        for (int i = 0; i < n; i++)
        {
            dp[mask][i] = INF;
        }
    }
    dp[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((mask >> i) & 1)
            {
                for (int j = 0; j < n; j++)
                {
                    if (!((mask >> j) & 1) && cost[i][j] > 0)
                    {
                        dp[mask ^ (1 << j)][j] = min(dp[mask ^ (1 << j)][j], dp[mask][i] + cost[i][j]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 1; i < n; i++)
    {
        if (cost[i][0] > 0)
        {
            ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
        }
    }
    fout << ans;
    return 0;
}