#include <fstream>

using namespace std;

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

const int N = 20;
const unsigned f_mare = 4e9;
int c[N][N], n, m, i, j, k, cost, x, y;
unsigned dp[(1<<18)+5][N];

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> cost;
        c[x][y] = cost;
    }

    for (i = 1; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            dp[i][j] = f_mare;

    dp[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 (j != k && (i&(1<<k)) != 0 && c[k][j])
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][k] + c[k][j]);

    unsigned min1 = f_mare;
    for (i = 1; i < n; i++)
        if (c[i][0])
            min1 = min(min1, dp[(1<<n)-1][i] + c[i][0]);

    g << min1;

    return 0;
}