#include <fstream>

using namespace std;

int conf, n, m, i, j, x, y, c;
long long C[270000][18], Cost[18][18], sol;
int main()
{
    ifstream fi("hamilton.in");
    ofstream fo("hamilton.out");
    fi >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fi >> x >> y >> c;
        Cost[x][y] = c;
    }
    C[1][0] = 0;
    for(conf = 2; conf < (1<<n); conf++)
        for(i = 0; i < n; i++)
        if((1<<i) & conf)
        {
            C[conf][i] = (1LL << 50);
            for(j = 0; j < n; j++)
            if(((1<<j) & conf) and Cost[j][i])
                C[conf][i] = min(C[conf][i], C[conf ^ (1<<i)][j] + Cost[j][i]);
        }
    sol = (1LL<<50);
    conf = (1<<n) - 1;
    for(i = 1; i < n; i++)
        if(Cost[i][0]) sol = min(sol, C[conf][i] + Cost[i][0]);
    fo << sol << "\n";
    return 0;
}