#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf = (1 << 30);
int n, m, x, y, cst[20][20], dp[(1 << 20)][20], solmin = inf;
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        fin >> cst[x][y];
    }
    for(int i = 0 ; i < (1 << n); i++)
        for(int j = 0 ; j < n; j++)
            dp[i][j] = inf;
    dp[1][0] =  0;
    for(int mask = 1; mask < (1 << n); mask++)
    {
        for(int i = 0 ; i < n; i++)
            if(mask & (1 << i))
            {
                for(int j = 0 ; j < n; j++)
                {
                    if((mask & (1 << j)) == 0 && cst[i][j])
                        dp[mask + (1 << j)][j] = min(dp[mask][i] + cst[i][j], dp[mask + (1 << j)][j]);
                }
            }
    }
    solmin = inf;
    for(int i = 0 ; i < n; i++)
        if(cst[i][0])
            solmin = min(solmin, dp[(1 << n) - 1][i] + cst[i][0]);
    fout << solmin;
    return 0;
}