#include <fstream>
#include <vector>
#define NMAX 20

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

struct v
{
    int vecin, cost;
};

int dp[NMAX][(1 << 18)];
vector <v> adj[NMAX];

const int INF = 1e9 + 7;

int main()
{
    int n, m, i, j, k, a, b, c, mask;
    in >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        in >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    for (i = 0; i < NMAX; ++i)
        for (j = 0; j < (1 << 18); ++j)
            dp[i][j] = INF;

    dp[0][1] = 0;
    for (mask = 1; mask < ((1 << n) - 1); ++mask)
    {
        for (i = 0; i < n; ++i)
        {
            if ((mask & (1 << i)) != 0)
            {
                for (auto [vecin, cost]: adj[i])
                {
                    //int vecin = adj[i][j].vecin;
                    //int cost = adj[i][j].cost;
                    if ((mask & (1 << vecin)) == 0)
                    {
                        dp[vecin][mask + (1 << vecin)] = min(dp[vecin][mask + (1 << vecin)], dp[i][mask] + cost);
                    }
                }
            }
        }
    }

    int minn = INF;
    for (i = 1; i < n; ++i)
    {
        for (j = 0; j < adj[i].size(); ++j)
        {
            if (adj[i][j].vecin == 0)
                minn = min(minn, dp[i][(1 << n) - 1] + adj[i][j].cost);
        }
    }

    out << minn;
    return 0;
}