#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 19, MMAX = 18*17 + 2, inf = 19000001;
int n, m, cost[NMAX][NMAX], dp[(1<<NMAX)+2][NMAX], mn = inf;

void citire()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for (int st = 0; st < (1<<n); st++)
        for (int i = 0; i < n; i++)
            dp[st][i] = inf;
}

int main()
{
    citire();

    dp[1][0] = 0;
    for (int st = 1; st < (1<<n); st++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((1<<i) & st == 0 || dp[st][i] == inf) continue;
            for (int j = 0; j < n; j++)
            {
                if ((1<<j) & st == 0 || cost[i][j] == 0) continue;
                dp[st+(1<<j)][j] = min(dp[st+(1<<j)][j], dp[st][i] + cost[i][j]);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (dp[(1<<n)-1][i] != inf && cost[i][0])
            mn = min(mn, dp[(1<<n)-1][i] + cost[i][0]);
    }
    fout << mn;

    return 0;
}