#include <fstream>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int INF = 2e8;
int d[20][(1 << 18) + 5];
int cost[20][20];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(cost[i][j] == 0)
                cost[i][j] = INF;
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int mask = 0; mask < (1 << 20); mask++)
            d[i][mask] = INF;
    }
    d[0][1] = 0;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        for(int i = 0; i < n; i++)
        {
            if(d[i][mask] != INF)
            {
                for(int v = 0; v < n; v++)
                {
                    if((mask & (1 << v)) == 0)
                    {
                        d[v][(mask | (1 << v))] = min(d[v][(mask | (1 << v))], d[i][mask] + cost[i][v]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < n; i++)
    {
        ans = min(d[i][(1 << n) - 1] + cost[i][0], ans);
    }
    cout << ans;
}