#include <fstream>
#define LL long long

using namespace std;

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

const int nmax = 18;
const int f_mare = 2e9;
int sol[(1<<nmax)][nmax], maxim;
int c[nmax][nmax], n, m, k, i, j, x, y, z;

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> z;
        c[x][y] = z;
    }
    for (i = 1; i < (1<<n); i++)
        for (j = 0; j < n; j++)
            sol[i][j] = f_mare;

    sol[1][0] = 0;

    for (i = 1; i < (1<<n); i++)
        for (j = 0; j < n; j++)
            if ((i&(1<<j))!=0)
                for (k = 0; k < n; k++)
                    if (k != j && (i&(1<<k))!=0 && c[k][j])
                        sol[i][j] = min(sol[i][j], sol[i^(1<<j)][k] + c[k][j]);
    maxim = f_mare;
    for (i = 1; i < n; i++)
        if (c[i][0])
            maxim = min(maxim, sol[(1<<n)-1][i] + c[i][0]);
    g << maxim;
    return 0;
}