#include <fstream>

using namespace std;

int D[(1<<18)+10][18], cost[20][20];

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

int main()
{
    int inf = 100000000;
    int n, m;
    fin >> n >> m;
    for(int i = 0 ; i <= n ; i++)
    {
        for(int j = 0 ; j <= n ; j++)
        {
            cost[i][j] = inf;
        }
    }
    for(int i = 1 ; i <= m ; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for(int bitmask = 0 ; bitmask < (1<<n) ; bitmask++ )
    {
        for(int i = 0 ; i < n ; i++)
            D[bitmask][i] = inf;
    }

    for(int i = 1 ; i < n ; i++)
    {
        D[ (1<<i) + (1<<0) ][i] = cost[0][i];
    }

    for(int bitmask = 0 ; bitmask < (1<<n) ; bitmask++ )
    {
        for(int i = 0 ; i < n ; i++)
        {
            /// vrem sa calculam D[bitmask][i]
            if( ((1<<i) & bitmask) != 0 )
            {
                int bitmask_prec = bitmask - (1<<i);
                for(int j = 0 ; j < n ; j++)
                {
                    if( (bitmask_prec & (1<<j)) != 0 )
                    {
                        D[bitmask][i] = min( D[bitmask][i], D[bitmask_prec][j] + cost[j][i] );
                    }
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0 ; i < n ; i++)
    {
        ans = min( ans, D[(1<<n)-1][i] + cost[i][0] );
    }
    fout << ans;

    return 0;
}